On the Parameterized Complexity of Computing Graph Bisections

DOI10.1007/978-3-642-45043-3_8zbMath1318.68098OpenAlexW119774723MaRDI QIDQ2864292

Ondřej Suchý, Manuel Sorge, Andreas Emil Feldmann, René van Bevern

Publication date: 6 December 2013

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-45043-3_8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Bisection of bounded treewidth graphs by convolutions ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs ⋮ Unnamed Item ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs ⋮ On the Complexity of Computing the k-restricted Edge-connectivity of a Graph

This page was built for publication: On the Parameterized Complexity of Computing Graph Bisections