Combinatorics for smaller kernels: the differential of a graph
From MaRDI portal
Publication:476877
DOI10.1016/J.TCS.2014.10.007zbMATH Open1305.05216DBLPjournals/tcs/BermudoF15OpenAlexW2042274748WikidataQ59864906 ScholiaQ59864906MaRDI QIDQ476877FDOQ476877
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
Recommendations
approximation algorithmkernelizationparameterized algorithmcombinatorial boundsdifferential of a graph
Cites Work
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Approximation algorithms for the test cover problem
- Roman domination in graphs.
- Defending the Roman Empire---a new strategy
- Vertex packings: Structural properties and algorithms
- Title not available (Why is that?)
- Computing the differential of a graph: hardness, approximability and exact algorithms
- Enclaveless sets and MK-Systems
- Differentials in graphs
- Lower bounds on the differential of a graph
- Domination in graphs with minimum degree two
- Paths, Stars and the Number Three
- 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
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- 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
- The differential and the roman domination number of a graph
- Improved approximation algorithms for the spanning star forest problem
- An Improved Approximation Bound for Spanning Star Forest and Color Saving
- Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
Cited In (13)
- Unique response Roman domination versus 2-packing differential in complementary prisms
- On the differential polynomial of a graph
- Relations between the differential and parameters in graphs
- Minimal Roman dominating functions: extensions and enumeration
- \(\beta\)-differential of a graph
- On the differential and Roman domination number of a graph with minimum degree two
- On the complexity landscape of the domination chain
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Data reductions and combinatorial bounds for improved approximation algorithms
- Computing the differential of a graph: hardness, approximability and exact algorithms
- A proof of a conjecture on the differential of a subcubic graph
- Minimal Roman dominating functions: extensions and enumeration
- Differential in complementary prisms
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)
