Computing the differential of a graph: hardness, approximability and exact algorithms
From MaRDI portal
Publication:2448922
Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)
Recommendations
Cites work
- A fine-grained analysis of a simple independent set algorithm
- A measure \& conquer approach for the analysis of exact algorithms
- A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
- An approximation algorithm for maximum triangle packing
- An exact algorithm for the maximum leaf spanning tree problem
- An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- Combinatorial bounds via measure and conquer
- Differentials in graphs
- Efficiency in exponential time for domination-type problems
- Enclaveless sets and MK-Systems
- Exact algorithms for dominating set
- Exact exponential algorithms.
- Fast algorithms for max independent set
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- Inclusion/Exclusion Meets Measure and Conquer
- Lower bounds on the differential of a graph
- Matching theory
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Measure and conquer
- On feedback vertex sets and nonseparating independent sets in cubic graphs
- Optimization, approximation, and complexity classes
- Proof verification and the hardness of approximation problems
- Searching Trees: An Essay
- SOFSEM 2006: Theory and Practice of Computer Science
- Solving connected dominating set faster than \(2^n\)
- The toughness of split graphs
Cited in
(23)- On the differential polynomial of a graph
- A proof of a conjecture on the differential of a subcubic graph
- The differential of the line graph \(\mathcal{L} (G)\)
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- \(\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
- Relations between the differential and parameters in graphs
- Combinatorics for smaller kernels: the differential of a graph
- The differential of the strong product graphs
- Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs
- Minimal Roman dominating functions: extensions and enumeration
- Differential in complementary prisms
- Minimal Roman dominating functions: extensions and enumeration
- Unique response Roman domination versus 2-packing differential in complementary prisms
- The differential on graph operator \(\mathrm{R}(G)\)
- Distribution of the null coefficients of the differential polynomial of the tree graphs
- On the perfect differential and perfect Roman domination in complementary prisms
- Lower bounds on the differential of a graph
- On the differential of the graph operator \(\mathcal{S}_k (G)\)
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
- Data reductions and combinatorial bounds for improved approximation algorithms
This page was built for publication: Computing the differential of a graph: hardness, approximability and exact algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2448922)
