Combinatorics for smaller kernels: the differential of a graph

DOI10.1016/J.TCS.2014.10.007zbMath1305.05216DBLPjournals/tcs/BermudoF15OpenAlexW2042274748WikidataQ59864906 ScholiaQ59864906MaRDI QIDQ476877

Henning Fernau, Sergio Bermudo

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.10.007

zbMATH Keywords

approximation algorithmkernelizationparameterized algorithmcombinatorial boundsdifferential of a graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (10)

Relations between the differential and parameters in graphs ⋮ On the differential and Roman domination number of a graph with minimum degree two ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ Differential in complementary prisms ⋮ Data reductions and combinatorial bounds for improved approximation algorithms ⋮ On the differential polynomial of a graph ⋮ A proof of a conjecture on the differential of a subcubic graph ⋮ On the Complexity Landscape of the Domination Chain ⋮ \(\beta\)-differential of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bounds on the differential of a graph
• Approximation algorithms for the test cover problem
• Roman domination in graphs.
• Defending the Roman Empire---a new strategy
• Improved approximation algorithms for the spanning star forest problem
• Computing the differential of a graph: hardness, approximability and exact algorithms
• The differential and the roman domination number of a graph
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Domination in graphs with minimum degree two
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• Enclaveless sets and MK-Systems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Vertex packings: Structural properties and algorithms
• Paths, Stars and the Number Three
• Nonblocker in H-Minor Free Graphs: Kernelization Meets Discharging
• R<scp>OMAN DOMINATION</scp>: a parameterized perspective†
• SOFSEM 2006: Theory and Practice of Computer Science

This page was built for publication: Combinatorics for smaller kernels: the differential of a graph