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

DOI10.1137/16M1057152zbMath1358.05151arXiv1703.07964MaRDI QIDQ2968519

Hsueh-I Lu, Hung-Chun Liang

Publication date: 16 March 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.07964

zbMATH Keywords

minimum cut; girth; planar graph; shortest cycle

Mathematics Subject Classification ID

05C38: Paths and cycles

05C10: Planar graphs; geometric and topological aspects of graph theory

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

68P05: Data structures