Document Open Access Logo

Interval Query Problem on Cube-Free Median Graphs

Author Soh Kumabe

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.18.pdf
  • Filesize: 0.73 MB
  • 14 pages

Document Identifiers

Author Details

Soh Kumabe
  • The University of Tokyo, Japan

Acknowledgements

We are grateful to our supervisor Prof. Hiroshi Hirai for supporting our work. He gave us a lot of ideas to improve our paper. In particular, he simplified the proofs and helped us improve the introduction and the overall structure of this paper.

Cite AsGet BibTex

Soh Kumabe. Interval Query Problem on Cube-Free Median Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.18

Abstract

In this paper, we introduce the interval query problem on cube-free median graphs. Let G be a cube-free median graph and 𝒮 be a commutative semigroup. For each vertex v in G, we are given an element p(v) in 𝒮. For each query, we are given two vertices u,v in G and asked to calculate the sum of p(z) over all vertices z belonging to a u-v shortest path. This is a common generalization of range query problems on trees and grids. In this paper, we provide an algorithm to answer each interval query in O(log² n) time. The required data structure is constructed in O(n log³ n) time and O(n log² n) space. To obtain our algorithm, we introduce a new technique, named the staircases decomposition, to decompose an interval of cube-free median graphs into simpler substructures.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • Data Structures
  • Range Query Problems
  • Median Graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Stephen Alstrup, Cyril Gavoille, Haim Kaplan, and Theis Rauhe. Nearest common ancestors: a survey and a new distributed algorithm. In Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 258-264, 2002. Google Scholar
  2. S P Avann. Metric ternary distributive semi-lattices. Proceedings of the American Mathematical Society, 12(3):407-414, 1961. Google Scholar
  3. Hans-Jurgen Bandelt and Victor Chepoi. Metric graph theory and geometry: a survey. Contemporary Mathematics, 453:49-86, 2008. Google Scholar
  4. Michael A Bender and Martin Farach-Colton. The LCA problem revisited. In Latin American Symposium on Theoretical Informatics, pages 88-94, 2000. Google Scholar
  5. Michael A Bender, Martín Farach-Colton, Giridhar Pemmasani, Steven Skiena, and Pavel Sumazin. Lowest common ancestors in trees and directed acyclic graphs. Journal of Algorithms, 57(2):75-94, 2005. Google Scholar
  6. Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, and Yann Vaxès. Medians in median graphs and their cube complexes in linear time. In Proceedings of the Forty-Seventh International Colloquium on Automata, Languages, and Programming, page to appear, 2020. Google Scholar
  7. Garrett Birkhoff and Stephen A Kiss. A ternary operation in distributive lattices. Bulletin of the American Mathematical Society, 53(8):749-752, 1947. Google Scholar
  8. Gerth Stølting Brodal, Pooya Davoodi, and S Srinivasa Rao. Path minima queries in dynamic weighted trees. In Workshop on Algorithms and Data Structures, pages 290-301. Springer, 2011. Google Scholar
  9. Bernard Chazelle. Computing on a free tree via complexity-preserving mappings. Algorithmica, 2(1-4):337-361, 1987. Google Scholar
  10. Bernard Chazelle and Leonidas J Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1(1-4):133-162, 1986. Google Scholar
  11. Bernard Chazelle and Burton Rosenberg. Computing partial sums in multidimensional arrays. In Proceedings of the fifth annual symposium on Computational geometry, pages 131-139, 1989. Google Scholar
  12. Victor Chepoi. Classification of graphs by means of metric triangles. Metody Diskret. Analiz, 49:75-93, 1989. Google Scholar
  13. Victor Chepoi, Arnaud Labourel, and Sébastien Ratel. Distance labeling schemes for cube-free median graphs. In 44th International Symposium on Mathematical Foundations of Computer Science, pages 15:1-15:14, 2019. Google Scholar
  14. Victor Chepoi and Daniela Maftuleac. Shortest path problem in rectangular complexes of global nonpositive curvature. Computational Geometry, 46(1):51-64, 2013. Google Scholar
  15. Adam Clearwater, Clemens Puppe, and Arkadii Slinko. Generalizing the single-crossing property on lines and trees to intermediate preferences on median graphs. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015. Google Scholar
  16. Nadia Creignou and J-J Hébrard. On generating all solutions of generalized satisfiability problems. RAIRO-Theoretical Informatics and Applications, 31(6):499-511, 1997. Google Scholar
  17. Gabrielle Demange. Majority relation and median representative ordering. SERIEs: Journal of the Spanish Economic Association, 3(1):95-109, 2012. Google Scholar
  18. Harold N Gabow, Jon Louis Bentley, and Robert E Tarjan. Scaling and related techniques for geometry problems. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 135-143, 1984. Google Scholar
  19. Dan Gusfield. Algorithms on stings, trees, and sequences: Computer science and computational biology. Acm Sigact News, 28(4):41-60, 1997. Google Scholar
  20. Dov Harel and Robert E Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338-355, 1984. Google Scholar
  21. George S Lueker. A data structure for orthogonal range queries. In Proceedings of the nineteenth Annual Symposium on Foundations of Computer Science, pages 28-34, 1978. Google Scholar
  22. Henry Martyn Mulder and Alexander Schrijver. Median graphs and helly hypergraphs. Discrete Mathematics, 25(1):41-50, 1979. Google Scholar
  23. Ladislav Nebeskỳ. Median graphs. Commentationes Mathematicae Universitatis Carolinae, 12(2):317-325, 1971. Google Scholar
  24. David Peleg. Proximity-preserving labeling schemes. Journal of Graph Theory, 33(3):167-176, 2000. Google Scholar
  25. Clemens Puppe and Arkadii Slinko. Condorcet domains, median graphs and the single-crossing property. Economic Theory, 67(1):285-318, 2019. Google Scholar
  26. Thomas J Schaefer. The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pages 216-226, 1978. Google Scholar
  27. Andrew C Yao. Space-time tradeoff for answering range queries. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 128-136, 1982. Google Scholar
  28. Andrew C Yao. On the complexity of maintaining partial sums. SIAM Journal on Computing, 14(2):277-288, 1985. Google Scholar
  29. Hao Yuan and Mikhail J Atallah. Data structures for range minimum queries in multidimensional arrays. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 150-160, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact