On making a distinguished vertex of minimum degree by vertex deletion
DOI10.1007/S00453-012-9695-6zbMATH Open1360.68492DBLPjournals/algorithmica/BetzlerBBNU14OpenAlexW2048322630WikidataQ59567485 ScholiaQ59567485MaRDI QIDQ528861FDOQ528861
Authors: Nadja Betzler, Hans L. Bodlaender, Robert Bredereck, Rolf Niedermeier, Johannes Uhlmann 
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
Recommendations
- On making a distinguished vertex minimum degree by vertex deletion
- On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion
- On bounded-degree vertex deletion parameterized by treewidth
- A parameterized algorithm for bounded-degree vertex deletion
- On structural parameterizations of the bounded-degree vertex deletion problem
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- On problems without polynomial kernels
- A partial k-arboretum of graphs with bounded treewidth
- Parametrized complexity theory.
- Kernelization -- preprocessing with a guarantee
- A 4 k 2 kernel for feedback vertex set
- On feedback vertex set new measure and new structures
- Incompressibility through Colors and IDs
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Title not available (Why is that?)
- A generalization of Nemhauser and Trotter's local optimization theorem
- Clique relaxations in social network analysis: the maximum \(k\)-plex problem
- Infeasibility of instance compression and succinct PCPs for NP
- Treewidth. Computations and approximations
- A graph‐theoretic generalization of the clique concept
- On bounded-degree vertex deletion parameterized by treewidth
- New Races in Parameterized Algorithmics
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Kernel bounds for disjoint cycles and disjoint paths
- Title not available (Why is that?)
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- Reflections on multivariate algorithmics and problem parameterization
- The Structure and Number of Obstructions to Treewidth
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- Kernelization: new upper and lower bound techniques
- Towards fully multivariate algorithmics: some new results and directions in parameter ecology
- Parameterized complexity of candidate control in elections and related digraph problems
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Treewidth computations. II. Lower bounds
Cited In (5)
- On making a distinguished vertex minimum degree by vertex deletion
- Resolute control: forbidding candidates from winning an election is hard
- Making an arbitrary filled graph minimal by removing fill edges
- Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations
- On structural parameterizations of the bounded-degree vertex deletion problem
Uses Software
This page was built for publication: On making a distinguished vertex of minimum degree by vertex deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528861)
