2 Search Results for "Chiu, Yung-Chung"

Document
DOI: 10.4230/LIPIcs.STACS.2022.23
Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-Shortest Induced Paths

Authors: Yung-Chung Chiu and Hsueh-I Lu

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
For vertices u and v of an n-vertex graph G, a uv-trail of G is an induced uv-path of G that is not a shortest uv-path of G. Berger, Seymour, and Spirkl [Discrete Mathematics 2021] gave the previously only known polynomial-time algorithm, running in O(n^{18}) time, to either output a uv-trail of G or ensure that G admits no uv-trail. We reduce the complexity to the time required to perform a poly-logarithmic number of multiplications of n²× n² Boolean matrices, leading to a largely improved O(n^{4.75})-time algorithm.
Cite as

Yung-Chung Chiu and Hsueh-I Lu. Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-Shortest Induced Paths. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.STACS.2022.23,
  author =	{Chiu, Yung-Chung and Lu, Hsueh-I},
  title =	{{Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-Shortest Induced Paths}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.23},
  URN =		{urn:nbn:de:0030-drops-158333},
  doi =		{10.4230/LIPIcs.STACS.2022.23},
  annote =	{Keywords: Induced subgraph, induced path, non-shortest path, dynamic data structure}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.58
Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain

Authors: Elena Arseneva, Man-Kwun Chiu, Matias Korman, Aleksandar Markovic, Yoshio Okamoto, Aurélien Ooms, André van Renssen, and Marcel Roeloffzen

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

Abstract
We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O(min(n^omega, n^2 + nh log h + chi^2)) time, where omega<2.373 denotes the matrix multiplication exponent and chi in Omega(n) cap O(n^2) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O(n^2 log n) time.
Cite as

Elena Arseneva, Man-Kwun Chiu, Matias Korman, Aleksandar Markovic, Yoshio Okamoto, Aurélien Ooms, André van Renssen, and Marcel Roeloffzen. Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 58:1-58:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{arseneva_et_al:LIPIcs.ISAAC.2018.58,
  author =	{Arseneva, Elena and Chiu, Man-Kwun and Korman, Matias and Markovic, Aleksandar and Okamoto, Yoshio and Ooms, Aur\'{e}lien and van Renssen, Andr\'{e} and Roeloffzen, Marcel},
  title =	{{Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{58:1--58:13},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.58},
  URN =		{urn:nbn:de:0030-drops-100060},
  doi =		{10.4230/LIPIcs.ISAAC.2018.58},
  annote =	{Keywords: Rectilinear link distance, polygonal domain, diameter, radius}
}
  • Refine by Author
  • 1 Arseneva, Elena
  • 1 Chiu, Man-Kwun
  • 1 Chiu, Yung-Chung
  • 1 Korman, Matias
  • 1 Lu, Hsueh-I
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Induced subgraph
  • 1 Rectilinear link distance
  • 1 diameter
  • 1 dynamic data structure
  • 1 induced path
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2022

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