Parameterized complexity of multi-node hubs

DOI10.1016/j.jcss.2022.08.001OpenAlexW2919942199MaRDI QIDQ2084737

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)

Related Items (1)

On the parameterized complexity of the Maximum Exposure Problem

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Maximum balanced subgraph problem parameterized above lower bound
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• A new algorithm for finding trees with many leaves
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Vertex and edge covers with clustering properties: Complexity and algorithms
• Optimization, approximation, and complexity classes
• Approximation algorithms for connected maximum cut and related problems
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Parameterized algorithms for graph partitioning problems
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• $$(k,n-k)$$ ( k , n - k ) -Max-Cut: An $${\mathcal O}^*(2^p)$$ O ∗ ( 2 p ) -Time Algorithm and a Polynomial Kernel
• Deterministic Parameterized Connected Vertex Cover
• Emergence of Scaling in Random Networks
• Authoritative sources in a hyperlinked environment
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Max-Cut Under Graph Constraints
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Color-coding
• 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
• Minimum bisection is fixed parameter tractable
• Algorithms and Data Structures
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Parameterized Algorithms

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