Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus

DOI10.1137/100811416zbMath1272.05102arXiv1004.4484OpenAlexW2078191188MaRDI QIDQ5891166

Viresh Patel

Publication date: 25 September 2013

Published in: SIAM Journal on Computing, Algorithms – ESA 2010 (Search for Journal in Brave)

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

zbMATH Keywords

homologygenusorientable surfacesparsest cutparameterized algorithmedge expansion

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (4)

Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem

This page was built for publication: Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus