Parameterized complexity of multi-node hubs

DOI10.1016/J.JCSS.2022.08.001MaRDI QIDQ2084737zbMATH OpenOpenAlexFDO

Authors Saket Saurabh, Meirav Zehavi

Publication date 13 October 2022

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2022.08.001

zbMATH Keywords

parameterized complexityhubbisection decomposition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Parameterized complexity of multi-node hubs
• Parameterized complexity of critical node cuts
• Parameterized complexity of critical node cuts
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems

Cites work

• scientific article; zbMATH DE number 1342117 (Why is no real title available?)
• A new algorithm for finding trees with many leaves
• Algorithms and Data Structures
• Approximation algorithms for maximization problems arising in graph partitioning
• Authoritative sources in a hyperlinked environment
• Balanced judicious bipartition is fixed-parameter tractable
• Color-coding
• Deterministic parameterized connected vertex cover
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Emergence of Scaling in Random Networks
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Fundamentals of parameterized complexity
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Max-cut under graph constraints
• Maximum balanced subgraph problem parameterized above lower bound
• Minimum bisection is fixed parameter tractable
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Optimization, approximation, and complexity classes
• Parameterized algorithms
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Reducing CMSO model checking to highly connected graphs
• Vertex and edge covers with clustering properties: Complexity and algorithms
• \((k,n-k)\)-max-cut: an \({\mathcal O}^*(2^p)\)-time algorithm and a polynomial kernel
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound

Cited in

(1)

• On the parameterized complexity of the Maximum Exposure Problem

This page was built for publication: Parameterized complexity of multi-node hubs

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