Parameterized Power Vertex Cover

DOI10.1007/978-3-662-53536-3_9zbMath1417.05157arXiv1801.10476OpenAlexW2525913907MaRDI QIDQ3181050

Michael Lampis, Bruno Escoffier, Eric Angel, Evripidis Bampis

Publication date: 22 December 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1801.10476

zbMATH Keywords

treewidthparameterized complexityparameterized approximationpower vertex cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (9)

Unnamed Item ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Approximating power node-deletion problems ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Parameterized (Approximate) Defective Coloring ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions ⋮ Unnamed Item ⋮ Structurally parameterized \(d\)-scattered set ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Improved upper bounds for vertex cover
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• A kernel of order \(2k-c\log k\) for vertex cover
• Parameterized complexity of Vertex Cover variants
• Crown reductions for the minimum weighted vertex cover problem
• Deterministic Parameterized Connected Vertex Cover
• The Design of Approximation Algorithms
• Min-Power Covering Problems
• Capacitated Domination and Covering: A Parameterized Perspective
• On efficient fixed-parameter algorithms for weighted vertex cover
• Parameterized Approximation Schemes Using Graph Widths
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Parameterized Power Vertex Cover