On making a distinguished vertex of minimum degree by vertex deletion
From MaRDI portal
Publication:528861
DOI10.1007/s00453-012-9695-6zbMath1360.68492OpenAlexW2048322630WikidataQ59567485 ScholiaQ59567485MaRDI QIDQ528861
Hans L. Bodlaender, Nadja Betzler, Rolf Niedermeier, Johannes Uhlmann, Robert Bredereck
Publication date: 17 May 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9695-6
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)
Related Items
Resolute control: forbidding candidates from winning an election is hard ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Treewidth computations. II. Lower bounds
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- A generalization of Nemhauser and Trotter's local optimization theorem
- On bounded-degree vertex deletion parameterized by treewidth
- On problems without polynomial kernels
- Parameterized complexity of candidate control in elections and related digraph problems
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth. Computations and approximations
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Parametrized complexity theory.
- Kernelization – Preprocessing with a Guarantee
- New Races in Parameterized Algorithmics
- A 4 k 2 kernel for feedback vertex set
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- Reflections on Multivariate Algorithmics and Problem Parameterization
- The Structure and Number of Obstructions to Treewidth
- On Feedback Vertex Set New Measure and New Structures
- Incompressibility through Colors and IDs
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
- Kernelization: New Upper and Lower Bound Techniques
- A graph‐theoretic generalization of the clique concept
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
