A faster algorithm for computing the girth of planar and bounded genus graphs

DOI10.1145/1868237.1868240zbMath1295.05229OpenAlexW1990428898MaRDI QIDQ3188984

Hristo N. Djidjev

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1868237.1868240

zbMATH Keywords

cyclesplanar graphsgirthshortest pathsgraph algorithmsdynamic algorithmsgraph genusgraph separatorspath and circuit problemshammock decomposition

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths

This page was built for publication: A faster algorithm for computing the girth of planar and bounded genus graphs