Combinatorics for smaller kernels: the differential of a graph

DOI10.1016/J.TCS.2014.10.007MaRDI QIDQ476877zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Sergio Bermudo, Henning Fernau

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)

Recommendations

• On the differential in graphs
• Bounds on the differential of a graph
• Lower bounds on the differential of a graph
• \(\beta\)-differential of a graph
• Differentials in certain classes of graphs

Cites work

• [article; zbMATH DE number 1161563 (Why is no real title available?)]
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for the test cover problem
• Computing the differential of a graph: hardness, approximability and exact algorithms
• Defending the Roman Empire---a new strategy
• Differentials in graphs
• Domination in graphs with minimum degree two
• Enclaveless sets and MK-Systems
• Improved approximation algorithms for the spanning star forest problem
• Lower bounds on the differential of a graph
• Nonblocker in \(H\)-minor free graphs: kernelization meets discharging
• On the Size of Systems of Sets Every <i>t</i> of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Paths, Stars and the Number Three
• R<scp>OMAN DOMINATION</scp>: a parameterized perspective†
• Roman domination in graphs.
• SOFSEM 2006: Theory and Practice of Computer Science
• The differential and the roman domination number of a graph
• Vertex packings: Structural properties and algorithms

Cited in

(13)

• Differential in complementary prisms
• Minimal Roman dominating functions: extensions and enumeration
• 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
• On the complexity landscape of the domination chain
• Unique response Roman domination versus 2-packing differential in complementary prisms
• Data reductions and combinatorial bounds for improved approximation algorithms
• Computing the differential of a graph: hardness, approximability and exact algorithms
• \(\beta\)-differential of a graph
• Minimal Roman dominating functions: extensions and enumeration
• On the differential polynomial of a graph
• A proof of a conjecture on the differential of a subcubic graph

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476877)