DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.13

Computation of Cycle Bases in Surface Embedded Graphs

Authors: Kyle Fox and Thomas Stanley

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

Abstract

We present an O(n³ g²log g + m) + Õ(n^{ω + 1}) time deterministic algorithm to find the minimum cycle basis of a directed graph embedded on an orientable surface of genus g. This result improves upon the previous fastest known running time of O(m³n + m²n² log n) applicable to general directed graphs. While an O(n^ω + 2^{2g}n² + m) time deterministic algorithm was known for undirected graphs, the use of the underlying field ℚ in the directed case (as opposed to ℤ₂ for the undirected case) presents extra challenges. It turns out that some of our new observations are useful for both variants of the problem, so we present an O(n^ω + n² g² log g + m) time deterministic algorithm for undirected graphs as well.

Cite as

Kyle Fox and Thomas Stanley. Computation of Cycle Bases in Surface Embedded Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.ISAAC.2022.13,
  author =	{Fox, Kyle and Stanley, Thomas},
  title =	{{Computation of Cycle Bases in Surface Embedded Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{13:1--13:13},
  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.13},
  URN =		{urn:nbn:de:0030-drops-172982},
  doi =		{10.4230/LIPIcs.ISAAC.2022.13},
  annote =	{Keywords: cycle basis, surface embedded graphs, homology}
}

Search Results

Documents authored by Stanley, Thomas

Computation of Cycle Bases in Surface Embedded Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message