Parameterized complexity of generalizations of edge dominating set

DOI10.1007/S00224-026-10288-5MaRDI QIDQ7317163zbMATH OpenFDO

Authors Shubhada Aute, Fahad Panolan, Souvik Saha, Saket Saurabh, Anannya Upasana

Publication date 21 August 2026

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00224-026-10288-5

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Cites work

• A 2-approximation algorithm for the minimum weight edge dominating set problem
• A faster algorithm for vertex cover parameterized by solution size
• A kernel of order \(2k - c\) for Vertex Cover
• A kernel of order 2k-c k for vertex cover
• A refined exact algorithm for edge dominating set
• A threshold of ln n for approximating set cover
• An Algorithm for a Minimum Cover of a Graph
• An efficient fixed-parameter algorithm for 3-hitting set
• An improved algorithm for parameterized edge dominating set problem
• Analytical approach to parallel repetition
• Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract)
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Edge Dominating Sets in Graphs
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Exact Algorithms for Edge Domination
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• Improved Parameterized Upper Bounds for Vertex Cover
• Kernels for edge dominating set: simpler or smaller
• New Parameterized Algorithms for the Edge Dominating Set Problem
• New results on polynomial inapproximability and fixed parameter approximability of \textsc{Edge Dominating Set}
• On two techniques of combining branching and treewidth
• Parameterized algorithms
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• Reducibility among combinatorial problems
• Set partitioning via inclusion-exclusion
• The union of minimal hitting sets: parameterized combinatorial bounds and counting
• Towards optimal and expressive kernelization for \(d\)-hitting set

This page was built for publication: Parameterized complexity of generalizations of edge dominating set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7317163)