On making a distinguished vertex of minimum degree by vertex deletion

DOI10.1007/S00453-012-9695-6MaRDI QIDQ528861zbMATH OpenOpenAlexDBLPWikidataFDO

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

zbMATH Keywords

graph modification problemparameterized complexitytreewidth

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

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

Cites work

• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A 4k^2 kernel for feedback vertex set
• A generalization of Nemhauser and Trotter's local optimization theorem
• A graph‐theoretic generalization of the clique concept
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Clique relaxations in social network analysis: the maximum k-plex problem
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Incompressibility through Colors and IDs
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• Kernelization -- preprocessing with a guarantee
• Kernelization: new upper and lower bound techniques
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• New races in parameterized algorithmics
• On bounded-degree vertex deletion parameterized by treewidth
• On feedback vertex set new measure and new structures
• On problems without polynomial kernels
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Parameterized complexity of candidate control in elections and related digraph problems
• Parametrized complexity theory.
• Reflections on multivariate algorithmics and problem parameterization
• The Structure and Number of Obstructions to Treewidth
• Towards fully multivariate algorithmics: some new results and directions in parameter ecology
• Treewidth computations. II. Lower bounds
• Treewidth. Computations and approximations

Cited in

(7)

• Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations
• Resolute control: forbidding candidates from winning an election is hard
• On structural parameterizations of the bounded-degree vertex deletion problem
• On making a distinguished vertex minimum degree by vertex deletion
• Making an arbitrary filled graph minimal by removing fill edges
• Hardness of bounding influence via graph modification
• Structural parameterizations for two bounded degree problems revisited

Describes a project that uses

Uses Software

• ComputeTW

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)