Circuit complexity of properties of graphs with constant planar cutwidth

DOI10.1007/978-3-662-44465-8_29MaRDI QIDQ2922620zbMATH OpenOpenAlexFDO

Authors Kristoffer Arnsfelt Hansen, Balagopal Komarath, Jayalal Sarma M. N., Sven Skyum, Navid Talebanfard

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44465-8_29

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The complexity of the matching-cut problem for planar graphs and other graph classes
• Lower bounds for dynamic programming on planar graphs of bounded cutwidth
• The complexity of counting in sparse, regular, and planar graphs
• Lower bounds for dynamic programming on planar graphs of bounded cutwidth
• The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract)

Cited in

(2)

• Constant width planar computation characterizes ACC\(^{0}\)
• STACS 2004

This page was built for publication: Circuit complexity of properties of graphs with constant planar cutwidth

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