scientific article; zbMATH DE number 7559145
From MaRDI portal
Publication:5090486
DOI10.4230/LIPIcs.STACS.2019.36MaRDI QIDQ5090486
Stefan Kratsch, Eva-Maria C. Hols
Publication date: 18 July 2022
Full work available at URL: https://arxiv.org/abs/1901.03582
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Cites Work
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Parameterized edge dominating set in graphs with degree bounded by 3
- New parameterized algorithms for the edge dominating set problem
- A refined exact algorithm for edge dominating set
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Infeasibility of instance compression and succinct PCPs for NP
- Approximating edge dominating set in dense graphs
- Improved approximation bounds for edge dominating set in dense graphs
- On two techniques of combining branching and treewidth
- On problems without polynomial kernels
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Edge dominating set and colorings on graphs with fixed clique-width
- Exact algorithms for edge domination
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- Approximation hardness of edge dominating set problems
- Efficient exact algorithms through enumerating maximal independent sets and other techniques
- An Improved Algorithm for Parameterized Edge Dominating Set Problem
- On Multiway Cut Parameterized above Lower Bounds
- Kernels for Edge Dominating Set: Simpler or Smaller
- Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
- Paths, Flowers and Vertex Cover
- Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
- Edge Dominating Sets in Graphs
- Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
- A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
- On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets
- Faster Parameterized Algorithms Using Linear Programming
- Kernelization Lower Bounds by Cross-Composition
- An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
