Parameterized Complexity of Multi-Node Hubs

DOI10.4230/LIPIcs.IPEC.2018.8OpenAlexW2946123130MaRDI QIDQ5009470

Meirav Zehavi, Saket Saurabh

Publication date: 4 August 2021

Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2019/10209/pdf/LIPIcs-IPEC-2018-8.pdf

zbMATH Keywords

tree decompositionbisectionhub

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx)

Related Items (1)

Computing the largest bond and the maximum connected cut of a graph

Cites Work

• A new algorithm for finding trees with many leaves
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Optimization, approximation, and complexity classes
• Approximation algorithms for connected maximum cut and related problems
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Parameterized algorithms for graph partitioning problems
• $$(k,n-k)$$ ( k , n - k ) -Max-Cut: An $${\mathcal O}^*(2^p)$$ O ∗ ( 2 p ) -Time Algorithm and a Polynomial Kernel
• Authoritative sources in a hyperlinked environment
• Max-Cut Under Graph Constraints
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Reducing CMSO model checking to highly connected graphs
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• Algorithms and Data Structures
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

This page was built for publication: Parameterized Complexity of Multi-Node Hubs