Minimum cuts and shortest homologous cycles

DOI10.1145/1542362.1542426zbMath1388.05177OpenAlexW2066108505MaRDI QIDQ5370738

Amir Nayyeri, Jeff Erickson, Erin Wolf Chambers

Publication date: 20 October 2017

Published in: Proceedings of the twenty-fifth annual symposium on Computational geometry (Search for Journal in Brave)

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

zbMATH Keywords

computational topologytopological graph theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Minimum Cuts in Surface Graphs ⋮ Computing the shortest essential cycle ⋮ Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ Hardness results for homology localization ⋮ Non total-unimodularity neutralized simplicial complexes ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ Topologically trivial closed walks in directed surface graphs ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Unnamed Item ⋮ Computational topology and the Unique Games Conjecture ⋮ Unnamed Item ⋮ Lexicographic optimal homologous chains and applications to point cloud triangulations ⋮ Discrete systolic inequalities and decompositions of triangulated surfaces

This page was built for publication: Minimum cuts and shortest homologous cycles