Parameterized edge dominating set in graphs with degree bounded by 3

DOI10.1016/j.tcs.2012.08.015zbMath1325.05132OpenAlexW2000108275MaRDI QIDQ388085

Hiroshi Nagamochi, Mingyu Xiao

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

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

Related Items (7)

A Multivariate Approach for Weighted FPT Algorithms ⋮ A multivariate framework for weighted FPT algorithms ⋮ A refined exact algorithm for edge dominating set ⋮ Maximum matching and kernelization of edge dominating set ⋮ Unnamed Item ⋮ Upper and lower bounds on approximating weighted mixed domination ⋮ New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set

Cites Work

• Unnamed Item
• On two techniques of combining branching and treewidth
• On generating all maximal independent sets
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Parameterized Edge Dominating Set in Cubic Graphs
• Enumerate and Measure: Improving Parameter Budget Management
• Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
• A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Exact Algorithms for Edge Domination
• Maximum Independent Set in Graphs of Average Degree at Most Three in ${\mathcal O}(1.08537^n)$
• A Note on Vertex Cover in Graphs with Maximum Degree 3
• An Improved Exact Algorithm for Cubic Graph TSP
• Edge Dominating Sets in Graphs
• New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set

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