Parameterized edge dominating set in graphs with degree bounded by 3
From MaRDI portal
Publication:388085
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
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
