On Making a Distinguished Vertex Minimum Degree by Vertex Deletion

DOI10.1007/978-3-642-18381-2_10zbMath1298.68107OpenAlexW1560183925MaRDI QIDQ3075510

Robert Bredereck, Johannes Uhlmann, Nadja Betzler, Rolf Niedermeier

Publication date: 15 February 2011

Published in: SOFSEM 2011: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-18381-2_10

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex degrees (05C07)

Related Items (4)

Studies in Computational Aspects of Voting ⋮ On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion ⋮ Binary linear programming solutions and non-approximability for control problems in voting systems ⋮ On bounded-degree vertex deletion parameterized by treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On problems without polynomial kernels
• Parameterized complexity of candidate control in elections and related digraph problems
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• Incompressibility through Colors and IDs
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• Kernelization: New Upper and Lower Bound Techniques
• A Generalization of Nemhauser and Trotter's Local Optimization Theorem.

This page was built for publication: On Making a Distinguished Vertex Minimum Degree by Vertex Deletion