New parameterized algorithms for the edge dominating set problem

DOI10.1016/J.TCS.2012.06.022MaRDI QIDQ392035zbMATH OpenOpenAlexWikidataFDO

Authors Mingyu Xiao, Ton Kloks, Sheung-Hung Poon

Publication date 13 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.06.022

zbMATH Keywords

graph algorithmskernelizationparameterized algorithmsedge dominating set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• New Parameterized Algorithms for the Edge Dominating Set Problem
• An improved algorithm for parameterized edge dominating set problem
• An improved algorithm for parameterized edge dominating set problem
• Kernels for edge dominating set: simpler or smaller
• Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• A refined exact algorithm for edge dominating set
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• Edge Dominating Sets in Graphs
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Enumerate and measure: improving parameter budget management
• Exact Algorithms for Edge Domination
• Improved approximation bounds for edge dominating set in dense graphs
• On cliques in graphs
• On generating all maximal independent sets
• On two techniques of combining branching and treewidth
• Parameterized edge dominating set in cubic graphs (extended abstract)
• edge dominating set: Efficient Enumeration-Based Exact Algorithms

Cited in

(27)

• On approximating (connected) 2-edge dominating set by a tree
• New results on polynomial inapproximability and fixed parameter approximability of \textsc{Edge Dominating Set}
• On approximating (connected) 2-edge dominating set by a tree
• Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
• A multivariate approach for weighted FPT algorithms
• An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set
• Space limited graph algorithms on big data
• New Parameterized Algorithms for the Edge Dominating Set Problem
• Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
• Kernels for edge dominating set: simpler or smaller
• Improved parameterized algorithms and kernels for mixed domination
• A multivariate framework for weighted FPT algorithms
• Parameterized edge dominating set in graphs with degree bounded by 3
• Parameterized algorithms for edge biclique and related problems
• Partial vs. Complete Domination: t-Dominating Set
• Space limited linear-time graph algorithms on big data
• An improved algorithm for parameterized edge dominating set problem
• An improved algorithm for parameterized edge dominating set problem
• On kernelization for edge dominating set under structural parameters
• Kernelization of edge perfect code and its variants
• Parameterized edge dominating set in cubic graphs (extended abstract)
• New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
• Upper and lower bounds on approximating weighted mixed domination
• New results on directed edge dominating set
• Maximum matching and kernelization of edge dominating set
• A refined exact algorithm for edge dominating set
• edge dominating set: Efficient Enumeration-Based Exact Algorithms

This page was built for publication: New parameterized algorithms for the edge dominating set problem

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