On a generalization of Nemhauser and Trotter's local optimization theorem
DOI10.1016/j.jcss.2016.08.003zbMath1353.68138arXiv1601.00164OpenAlexW2231757830MaRDI QIDQ340561
Publication date: 14 November 2016
Published in: Journal of Computer and System Sciences, Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1601.00164
graph theorygraph algorithmsgraph decompositionkernelizationfixed-parameter tractablebounded-degree vertex deletion
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- A generalization of Nemhauser and Trotter's local optimization theorem
- On bounded-degree vertex deletion parameterized by treewidth
- Looking at the stars
- Isolation concepts for efficiently enumerating dense subgraphs
- An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
- Crown structures for vertex cover kernelization
- Crown reductions for the minimum weighted vertex cover problem
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Vertex Cover: Further Observations and Further Improvements
- A Parameterized Algorithm for Bounded-Degree Vertex Deletion
- A 4 k 2 kernel for feedback vertex set
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- An Extension of the Nemhauser–Trotter Theorem to Generalized Vertex Cover with Applications
- A Note on Vertex Cover in Graphs with Maximum Degree 3
- A Linear Kernel for Co-Path/Cycle Packing
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Vertex packings: Structural properties and algorithms
- A graph‐theoretic generalization of the clique concept
- Improved Algorithms for Bipartite Network Flow
- Faster Parameterized Algorithms Using Linear Programming
- A Generalization of Nemhauser and Trotter's Local Optimization Theorem.
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Graph-Theoretic Concepts in Computer Science