$$(k,n-k)$$ ( k , n - k ) -Max-Cut: An $${\mathcal O}^*(2^p)$$ O ∗ ( 2 p ) -Time Algorithm and a Polynomial Kernel

DOI10.1007/978-3-662-49529-2_51zbMath1475.68252OpenAlexW2471680335MaRDI QIDQ2802978

Meirav Zehavi, Saket Saurabh

Publication date: 3 May 2016

Published in: LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-49529-2_51

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (6)

Fast Distributed Approximation for Max-Cut ⋮ Parameterized algorithms for graph partitioning problems ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Parameterized Complexity of Multi-Node Hubs ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Parameterized complexity of multi-node hubs

This page was built for publication: $$(k,n-k)$$ ( k , n - k ) -Max-Cut: An $${\mathcal O}^*(2^p)$$ O ∗ ( 2 p ) -Time Algorithm and a Polynomial Kernel