Parameterized edge dominating set in graphs with degree bounded by 3

DOI10.1016/J.TCS.2012.08.015MaRDI QIDQ388085zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Hiroshi Nagamochi

Publication date 19 December 2013

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

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

zbMATH Keywords

cubic graphsparameterized algorithmedge dominating set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Parameterized edge dominating set in cubic graphs (extended abstract)
• Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
• An improved algorithm for parameterized edge dominating set problem
• New parameterized algorithms for the edge dominating set problem
• New Parameterized Algorithms for the Edge Dominating Set Problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A note on vertex cover in graphs with maximum degree 3
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• An Improved Exact Algorithm for Cubic Graph TSP
• 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
• Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
• Maximum Independent Set in graphs of average degree at most three in \({\mathcal O}(1.08537^n)\)
• New results on polynomial inapproximability and fixed parameter approximability of \textsc{Edge Dominating Set}
• 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

(13)

• Parameterized complexity of three edge contraction problems with degree constraints
• Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
• A multivariate approach for weighted FPT algorithms
• SOFSEM 2006: Theory and Practice of Computer Science
• A multivariate framework for weighted FPT algorithms
• 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
• 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
• Maximum matching and kernelization of edge dominating set
• A refined exact algorithm for edge dominating set

This page was built for publication: Parameterized edge dominating set in graphs with degree bounded by 3

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