Bisections above Tight Lower Bounds

DOI10.1007/978-3-642-34611-8_20zbMath1341.05214OpenAlexW92894981MaRDI QIDQ5200505

Rico Zenklusen, Matthias Mnich

Publication date: 6 November 2012

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-34611-8_20

zbMATH Keywords

exponential time hypothesis

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (8)

Satisfying more than half of a system of linear equations over GF(2): a multivariate approach ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ \textsc{Max-Cut} parameterized above the Edwards-Erdős bound ⋮ An improved kernel for max-bisection above tight lower bound ⋮ Large Independent Sets in Subquartic Planar Graphs ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable

This page was built for publication: Bisections above Tight Lower Bounds