Parameterized edge dominating set in graphs with degree bounded by 3
From MaRDI portal
Publication:388085
DOI10.1016/j.tcs.2012.08.015zbMath1325.05132MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Unnamed Item, Upper and lower bounds on approximating weighted mixed domination, A refined exact algorithm for edge dominating set, Maximum matching and kernelization of edge dominating set, New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set, A multivariate framework for weighted FPT algorithms, A Multivariate Approach for Weighted FPT Algorithms
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
