Parameterized complexity of multi-node hubs
type: Item
instance of: scholarly article
title: Parameterized complexity of multi-node hubs
author: Saket Saurabh
author: Meirav Zehavi
published in: Journal of Computer and System Sciences
publication date: 2022-10-13T00:00:00Z
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7601249
zbMATH Keywords: hub
zbMATH Keywords: parameterized complexity
zbMATH Keywords: bisection decomposition
MaRDI profile type: Publication
full work available at URL: j.jcss.2022.08.001
OpenAlex ID: W2919942199
cites work: Q4263699
cites work: Color-coding
cites work: Emergence of Scaling in Random Networks
cites work: Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
cites work: Maximum balanced subgraph problem parameterized above lower bound
cites work: \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
cites work: Deterministic Parameterized Connected Vertex Cover
cites work: Parameterized Algorithms
cites work: Minimum bisection is fixed parameter tractable
cites work: Fundamentals of parameterized complexity
cites work: Approximation algorithms for maximization problems arising in graph partitioning
cites work: Vertex and edge covers with clustering properties: Complexity and algorithms
cites work: Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Algorithms and Data Structures
cites work: Approximation algorithms for connected maximum cut and related problems
cites work: Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
cites work: Authoritative sources in a hyperlinked environment
cites work: A new algorithm for finding trees with many leaves
cites work: Max-Cut Under Graph Constraints
cites work: Reducing CMSO model checking to highly connected graphs
cites work: Balanced Judicious Bipartition is Fixed-Parameter Tractable
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
cites work: Optimization, approximation, and complexity classes
cites work: Improved fixed parameter tractable algorithms for two ``edge'' problems: MAXCUT and MAXDAG
cites work: $$(k,n-k)$$ ( k , n - k ) -Max-Cut: An $${\mathcal O}^*(2^p)$$ O ∗ ( 2 p ) -Time Algorithm and a Polynomial Kernel
cites work: Parameterized algorithms for graph partitioning problems
DOI: 10.1016/J.JCSS.2022.08.001
description: scientific article; zbMATH DE number 7601249