Minimum Edge Dominating Sets
From MaRDI portal
Publication:3136610
DOI10.1137/0406030zbMATH Open0782.05083OpenAlexW2083165612MaRDI QIDQ3136610FDOQ3136610
Authors: J. D. Horton, K. Kilakos 
Publication date: 14 October 1993
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0406030
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99)
Cited In (58)
- Algorithmic aspects of clique-transversal and clique-independent sets
- The Complexity of Computing the Random Priority Allocation Matrix
- Hardness and approximation results for some variants of stable marriage problem
- Smallest maximal matchings of graphs
- Improved approximation bounds for edge dominating set in dense graphs
- Complementary nil vertex edge dominating sets
- Approximability of the capacitated \(b\)-edge dominating set problem
- Minimum maximal matchings in cubic graphs
- Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
- The stable marriage problem with master preference lists
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Hardness and approximation of minimum maximal matchings
- A natural family of optimization problems with arbitrarily small approximation thresholds
- On the algorithmic complexity of edge total domination
- Aspects of upper defensive alliances
- Approximability results for stable marriage problems with ties.
- Integer programming formulations for the minimum weighted maximal matching problem
- Bounding and approximating minimum maximal matchings in regular graphs
- Linear time algorithms for generalized edge dominating set problems
- Improved budgeted connected domination and budgeted edge-vertex domination
- The complexity of total edge domination and some related results on trees
- Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
- Algorithmic aspects of upper edge domination
- Generalizing the induced matching by edge capacity constraints
- Approximation Algorithms for Facial Cycles in Planar Embeddings
- Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers
- New Results on Directed Edge Dominating Set
- Decomposition algorithms for solving the minimum weight maximal matching problem
- Complexity of finding graph roots with girth conditions
- Maximal matching and edge domination in complete multipartite graphs
- Small maximal matchings of random cubic graphs
- Complexity and characterization aspects of edge-related domination for graphs
- Approximating edge dominating set in dense graphs
- Modelling and solving the perfect edge domination problem
- On well-edge-dominated graphs
- Hard variants of stable marriage.
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
- Title not available (Why is that?)
- Using maximality and minimality conditions to construct inequality chains
- On the \(d\)-claw vertex deletion problem
- Maximal matching polytope in trees
- Domination versus edge domination
- On the complexity of variations of mixed domination on graphs†
- On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem
- Parameterized algorithms for stable matching with ties and incomplete lists
- Approximation algorithms for partially covering with edges
- A note on approximations of directed edge dominating set
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- On the semitotal domination number of line graphs
- Approximation hardness of edge dominating set problems
- Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
- Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames
- Algorithms and hardness results for edge total domination problem in graphs
- Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination
- On the \(d\)-claw vertex deletion problem
- Incidence‐free sets and edge domination in incidence graphs
This page was built for publication: Minimum Edge Dominating Sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3136610)
