On making a distinguished vertex of minimum degree by vertex deletion

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)

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

Title not available (Why is no real title available?)
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?)
A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
A generalization of Nemhauser and Trotter's local optimization theorem
A graph‐theoretic generalization of the clique concept
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
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

(6)

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

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)