Space complexity of optimization problems in planar graphs

DOI10.1007/978-3-319-06089-7_21MaRDI QIDQ5410651zbMATH OpenOpenAlexFDO

Authors Samir Datta, Raghav Kulkarni

Publication date 16 April 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-06089-7_21

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35)

Recommendations

• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Space complexity: what makes planar graphs special?
• Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Partitioning planar graphs: a fast combinatorial approach for max-cut
• Finding Separator Cuts in Planar Graphs within Twice the Optimal

Cited in

(5)

• Frameworks for designing in-place graph algorithms
• On the typical case complexity of graph optimization
• Design of algorithms for spatial-time reduction complexity of dynamic programming
• Space complexity: what makes planar graphs special?
• scientific article; zbMATH DE number 1822170 (Why is no real title available?)

This page was built for publication: Space complexity of optimization problems in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5410651)