Computing the differential of a graph: hardness, approximability and exact algorithms
From MaRDI portal
Publication:2448922
DOI10.1016/j.dam.2012.11.013zbMath1288.05262OpenAlexW2040446810MaRDI QIDQ2448922
Henning Fernau, Sergio Bermudo
Publication date: 5 May 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2012.11.013
Analysis of algorithms (68W40) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Relations between the differential and parameters in graphs ⋮ The differential of the line graph \(\mathcal{L} (G)\) ⋮ 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 ⋮ Combinatorics for smaller kernels: the differential of a graph ⋮ On the differential polynomial of a graph ⋮ A proof of a conjecture on the differential of a subcubic graph ⋮ Lower bounds on the differential of a graph ⋮ On the Complexity Landscape of the Domination Chain ⋮ The differential of the strong product graphs ⋮ \(\beta\)-differential of a graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exact algorithms for dominating set
- Exact exponential algorithms.
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- An exact algorithm for the maximum leaf spanning tree problem
- Lower bounds on the differential of a graph
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Solving connected dominating set faster than \(2^n\)
- Efficiency in exponential time for domination-type problems
- Matching theory
- Optimization, approximation, and complexity classes
- The toughness of split graphs
- Fast algorithms for max independent set
- An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}
- An approximation algorithm for maximum triangle packing
- A Fine-grained Analysis of a Simple Independent Set Algorithm
- Proof verification and the hardness of approximation problems
- A measure & conquer approach for the analysis of exact algorithms
- A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Measure and conquer
- Searching Trees: An Essay
- Inclusion/Exclusion Meets Measure and Conquer
- On feedback vertex sets and nonseparating independent sets in cubic graphs
- Enclaveless sets and MK-Systems
- Combinatorial bounds via measure and conquer
- SOFSEM 2006: Theory and Practice of Computer Science
