A generalization of Nemhauser and Trotter's local optimization theorem
From MaRDI portal
Publication:657921
DOI10.1016/j.jcss.2010.12.001zbMath1235.68081OpenAlexW2125455032WikidataQ57359675 ScholiaQ57359675MaRDI QIDQ657921
Michael R. Fellows, Jiong Guo, Rolf Niedermeier, Hannes Moser
Publication date: 11 January 2012
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.2010.12.001
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)
Related Items
Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths, Linear kernels for separating a graph into components of bounded size, Kernelization of the 3-path vertex cover problem, Approximating Bounded Degree Deletion via Matroid Matching, On the parameterized complexity of maximum degree contraction problem, Moderately exponential time algorithms for the maximum bounded-degree-1 set problem, Win-win kernelization for degree sequence completion problems, Isolation concepts for efficiently enumerating dense subgraphs, Edge-disjoint packing of stars and cycles, Graph isomorphism parameterized by elimination distance to bounded degree, Edge-Disjoint Packing of Stars and Cycles, On a generalization of Nemhauser and Trotter's local optimization theorem, A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion, A 2-approximation algorithm for the vertex coverP4problem in cubic graphs, Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs, On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem, A \(5k\)-vertex kernel for 3-path vertex cover, Approximating power node-deletion problems, Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs, Maximum weight t-sparse set problem on vector-weighted graphs, Kernelization and Parameterized Algorithms for 3-Path Vertex Cover, Parameterized complexity of three edge contraction problems with degree constraints, On structural parameterizations of the bounded-degree vertex deletion problem, A fixed-parameter algorithm for the vertex cover \(P_3\) problem, Multivariate algorithmics for finding cohesive subnetworks, Fixed-parameter algorithms for Vertex Cover \(P_3\), On the Parameterized Complexity of Maximum Degree Contraction Problem., On making a distinguished vertex of minimum degree by vertex deletion, Complexity and kernels for bipartition into degree-bounded induced graphs, A Parameterized Algorithm for Bounded-Degree Vertex Deletion, On bounded-degree vertex deletion parameterized by treewidth, Approximating Partially Bounded Degree Deletion on Directed Graphs, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}, Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Looking at the stars
- Isolation concepts for efficiently enumerating dense subgraphs
- A new approach for approximating node deletion problems
- Threshold dominating sets and an improved characterization of \(W[2\)]
- Reduction algorithms for graphs of small treewidth
- Crown structures for vertex cover kernelization
- Crown reductions for the minimum weighted vertex cover problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Parametrized complexity theory.
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Vertex Cover: Further Observations and Further Improvements
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- An Extension of the Nemhauser–Trotter Theorem to Generalized Vertex Cover with Applications
- Solving NP-hard semirandom graph problems in polynomial expected time
- An Improved Parameterized Algorithm for a Generalized Matching Problem
- A Linear Kernel for Co-Path/Cycle Packing
- Kernelization: New Upper and Lower Bound Techniques
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Vertex packings: Structural properties and algorithms
- A graph‐theoretic generalization of the clique concept
- A Generalization of Nemhauser and Trotter's Local Optimization Theorem.
- Graph-Theoretic Concepts in Computer Science
