New Results on Directed Edge Dominating Set

DOI10.4230/LIPIcs.MFCS.2018.67OpenAlexW2889284842MaRDI QIDQ5005171

Michael Lampis, Eun Jung Kim, Ioannis Katsikarelis, Tesshu Hanaka, Rémy Belmonte

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1902.04919

zbMATH Keywords

treewidthtournamentsedge dominating set

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (5)

Grundy Distinguishes Treewidth from Pathwidth ⋮ Unnamed Item ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ A note on approximations of directed edge dominating set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New parameterized algorithms for the edge dominating set problem
• A refined exact algorithm for edge dominating set
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Approximating edge dominating set in dense graphs
• Some properties of line digraphs
• On the parameterized complexity of multiple-interval graph problems
• Improved approximation bounds for edge dominating set in dense graphs
• On two techniques of combining branching and treewidth
• Some APX-completeness results for cubic graphs
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• The complexity of dissociation set problems in graphs
• Approximation hardness of edge dominating set problems
• An Improved Algorithm for Parameterized Edge Dominating Set Problem
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Kernels for Edge Dominating Set: Simpler or Smaller
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Enumerate and Measure: Improving Parameter Budget Management
• Minimum Edge Dominating Sets
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Edge Dominating Sets in Graphs
• Node-Deletion Problems on Bipartite Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments
• Optimal dynamic program for r-domination problems over tree decompositions
• Fixed-Parameter Tractability and Completeness I: Basic Results
• On Directed Covering and Domination Problems
• Analytical approach to parallel repetition
• Approximating k-center in planar graphs
• Parameterized Algorithms

This page was built for publication: New Results on Directed Edge Dominating Set