Search Results

Documents authored by Wu, Kaiyu

Document
DOI: 10.4230/LIPIcs.CPM.2024.17
Closing the Gap: Minimum Space Optimal Time Distance Labeling Scheme for Interval Graphs

Authors: Meng He and Kaiyu Wu

Published in: LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)

Abstract
We present a distance labeling scheme for an interval graph on n vertices that uses at most 3lg n + lg lg n + O(1) bits per vertex to answer distance queries, which ask for the distance between two given vertices, in constant time. Our labeling scheme improves the distance labeling scheme of Gavoille and Paul for connected interval graphs which uses at most 5lg n + O(1) bits per vertex to achieve constant query time. Our improved space cost matches a lower bound proven by Gavoille and Paul within additive lower order terms and is thus optimal. Based on this scheme, we further design a 6lg n + 2lg lg n +O(1) bit distance labeling scheme for circular-arc graphs, with constant distance query time, which improves the 10lg n + O(1) bit distance labeling scheme of Gavoille and Paul. We give a n/2 + O(lg^ 2n) bit labeling scheme for chordal graphs which answers distance queries in O(1) time. The best known lower bound is n/4 - o(n) bits.
Cite as

Meng He and Kaiyu Wu. Closing the Gap: Minimum Space Optimal Time Distance Labeling Scheme for Interval Graphs. In 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 296, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.CPM.2024.17,
  author =	{He, Meng and Wu, Kaiyu},
  title =	{{Closing the Gap: Minimum Space Optimal Time Distance Labeling Scheme for Interval Graphs}},
  booktitle =	{35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-326-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{296},
  editor =	{Inenaga, Shunsuke and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.17},
  URN =		{urn:nbn:de:0030-drops-201275},
  doi =		{10.4230/LIPIcs.CPM.2024.17},
  annote =	{Keywords: Distance Labeling, Interval Graph, Circular-Arc Graph, Chordal Graph}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.18
Distance Queries over Dynamic Interval Graphs

Authors: Jingbang Chen, Meng He, J. Ian Munro, Richard Peng, Kaiyu Wu, and Daniel J. Zhang

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
We design the first dynamic distance oracles for interval graphs, which are intersection graphs of a set of intervals on the real line, and for proper interval graphs, which are intersection graphs of a set of intervals in which no interval is properly contained in another. For proper interval graphs, we design a linear space data structure which supports distance queries (computing the distance between two query vertices) and vertex insertion or deletion in O(lg n) worst-case time, where n is the number of vertices currently in G. Under incremental (insertion only) or decremental (deletion only) settings, we design linear space data structures that support distance queries in O(lg n) worst-case time and vertex insertion or deletion in O(lg n) amortized time, where n is the maximum number of vertices in the graph. Under fully dynamic settings, we design a data structure that represents an interval graph G in O(n) words of space to support distance queries in O(n lg n/S(n)) worst-case time and vertex insertion or deletion in O(S(n)+lg n) worst-case time, where n is the number of vertices currently in G and S(n) is an arbitrary function that satisfies S(n) = Ω(1) and S(n) = O(n). This implies an O(n)-word solution with O(√{nlg n})-time support for both distance queries and updates. All four data structures can answer shortest path queries by reporting the vertices in the shortest path between two query vertices in O(lg n) worst-case time per vertex. We also study the hardness of supporting distance queries under updates over an intersection graph of 3D axis-aligned line segments, which generalizes our problem to 3D. Finally, we solve the problem of computing the diameter of a dynamic connected interval graph.
Cite as

Jingbang Chen, Meng He, J. Ian Munro, Richard Peng, Kaiyu Wu, and Daniel J. Zhang. Distance Queries over Dynamic Interval Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2023.18,
  author =	{Chen, Jingbang and He, Meng and Munro, J. Ian and Peng, Richard and Wu, Kaiyu and Zhang, Daniel J.},
  title =	{{Distance Queries over Dynamic Interval Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.18},
  URN =		{urn:nbn:de:0030-drops-193207},
  doi =		{10.4230/LIPIcs.ISAAC.2023.18},
  annote =	{Keywords: interval graph, proper interval graph, intersection graph, geometric intersection graph, distance oracle, distance query, shortest path query, dynamic graph}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.59
Shortest Beer Path Queries in Interval Graphs

Authors: Rathish Das, Meng He, Eitan Kondratovsky, J. Ian Munro, Anurag Murty Naredla, and Kaiyu Wu

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Our interest is in paths between pairs of vertices that go through at least one of a subset of the vertices known as beer vertices. Such a path is called a beer path, and the beer distance between two vertices is the length of the shortest beer path. We show that we can represent unweighted interval graphs using 2n log n + O(n) + O(|B|log n) bits where |B| is the number of beer vertices. This data structure answers beer distance queries in O(log^ε n) time for any constant ε > 0 and shortest beer path queries in O(log^ε n + d) time, where d is the beer distance between the two nodes. We also show that proper interval graphs may be represented using 3n + o(n) bits to support beer distance queries in O(f(n)log n) time for any f(n) ∈ ω(1) and shortest beer path queries in O(d) time. All of these results also have time-space trade-offs. Lastly we show that the information theoretic lower bound for beer proper interval graphs is very close to the space of our structure, namely log(4+2√3)n - o(n) (or about 2.9 n) bits.
Cite as

Rathish Das, Meng He, Eitan Kondratovsky, J. Ian Munro, Anurag Murty Naredla, and Kaiyu Wu. Shortest Beer Path Queries in Interval Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ISAAC.2022.59,
  author =	{Das, Rathish and He, Meng and Kondratovsky, Eitan and Munro, J. Ian and Naredla, Anurag Murty and Wu, Kaiyu},
  title =	{{Shortest Beer Path Queries in Interval Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{59:1--59:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.59},
  URN =		{urn:nbn:de:0030-drops-173442},
  doi =		{10.4230/LIPIcs.ISAAC.2022.59},
  annote =	{Keywords: Beer Path, Interval Graph}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.25
Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees

Authors: Meng He, J. Ian Munro, Yakov Nekrich, Sebastian Wild, and Kaiyu Wu

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
We present the first succinct distance oracles for (unweighted) interval graphs and related classes of graphs, using a novel succinct data structure for ordinal trees that supports the mapping between preorder (i.e., depth-first) ranks and level-order (breadth-first) ranks of nodes in constant time. Our distance oracles for interval graphs also support navigation queries - testing adjacency, computing node degrees, neighborhoods, and shortest paths - all in optimal time. Our technique also yields optimal distance oracles for proper interval graphs (unit-interval graphs) and circular-arc graphs. Our tree data structure supports all operations provided by different approaches in previous work, as well as mapping to and from level-order ranks and retrieving the last (first) internal node before (after) a given node in a level-order traversal, all in constant time.
Cite as

Meng He, J. Ian Munro, Yakov Nekrich, Sebastian Wild, and Kaiyu Wu. Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.ISAAC.2020.25,
  author =	{He, Meng and Munro, J. Ian and Nekrich, Yakov and Wild, Sebastian and Wu, Kaiyu},
  title =	{{Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{25:1--25:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.25},
  URN =		{urn:nbn:de:0030-drops-133693},
  doi =		{10.4230/LIPIcs.ISAAC.2020.25},
  annote =	{Keywords: succinct data structures, distance oracles, ordinal tree, level order, breadth-first order, interval graphs, proper interval graphs, succinct graph representation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.67
Succinct Data Structures for Chordal Graphs

Authors: J. Ian Munro and Kaiyu Wu

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We study the problem of approximate shortest path queries in chordal graphs and give a n log n + o(n log n) bit data structure to answer the approximate distance query to within an additive constant of 1 in O(1) time. We study the problem of succinctly storing a static chordal graph to answer adjacency, degree, neighbourhood and shortest path queries. Let G be a chordal graph with n vertices. We design a data structure using the information theoretic minimal n^2/4 + o(n^2) bits of space to support the queries: - whether two vertices u,v are adjacent in time f(n) for any f(n) in omega(1). - the degree of a vertex in O(1) time. - the vertices adjacent to u in (f(n))^2 time per neighbour - the length of the shortest path from u to v in O(nf(n)) time
Cite as

J. Ian Munro and Kaiyu Wu. Succinct Data Structures for Chordal Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 67:1-67:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{munro_et_al:LIPIcs.ISAAC.2018.67,
  author =	{Munro, J. Ian and Wu, Kaiyu},
  title =	{{Succinct Data Structures for Chordal Graphs}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{67:1--67:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.67},
  URN =		{urn:nbn:de:0030-drops-100153},
  doi =		{10.4230/LIPIcs.ISAAC.2018.67},
  annote =	{Keywords: Succinct Data Structure, Chordal Graph}
}
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 About DROPS Imprint Privacy Contact