Parameterized complexity of multi-node hubs
From MaRDI portal
Publication:2084737
DOI10.1016/J.JCSS.2022.08.001OpenAlexW2919942199MaRDI QIDQ2084737FDOQ2084737
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
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
Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Emergence of Scaling in Random Networks
- Fundamentals of parameterized complexity
- Optimization, approximation, and complexity classes
- Approximation algorithms for maximization problems arising in graph partitioning
- Authoritative sources in a hyperlinked environment
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Color-coding
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Parameterized algorithms
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Maximum balanced subgraph problem parameterized above lower bound
- A new algorithm for finding trees with many leaves
- Max-cut under graph constraints
- Title not available (Why is that?)
- Deterministic parameterized connected vertex cover
- Algorithms and Data Structures
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Minimum bisection is fixed parameter tractable
- Efficient computation of representative families with applications in parameterized and exact algorithms
- Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
- Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
- Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
- Reducing CMSO model checking to highly connected graphs
- Balanced judicious bipartition is fixed-parameter tractable
- \((k,n-k)\)-max-cut: an \({\mathcal O}^*(2^p)\)-time algorithm and a polynomial kernel
Cited In (1)
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)
