Perfect edge domination and efficient edge domination in graphs

DOI10.1016/S0166-218X(01)00198-6zbMath0995.05108OpenAlexW2092503911MaRDI QIDQ1613347

Chuan Yi Tang, Chin Lung Lu, Ming-Tat Ko

Publication date: 29 August 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00198-6

zbMATH Keywords

graph algorithmschordal graphsdominating setsefficient edge dominationperfect edge domination

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (31)

Perfect edge domination: hard and solvable cases ⋮ Efficient domination through eigenvalues ⋮ Kernelization of edge perfect code and its variants ⋮ Efficient and perfect domination on circular-arc graphs ⋮ Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time ⋮ Maximal matching and edge domination in complete multipartite graphs ⋮ Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs ⋮ Modelling and solving the perfect edge domination problem ⋮ Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time ⋮ Extended formulations for perfect domination problems and their algorithmic implications ⋮ Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time ⋮ Dominating induced matchings in graphs without a skew star ⋮ Dominating induced matchings for \(P_7\)-free graphs in linear time ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Complexity of simplicial homology and independence complexes of chordal graphs ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time ⋮ Fast algorithms for some dominating induced matching problems ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ Efficient domination for classes of \(P_6\)-free graphs ⋮ Minimum 2-tuple dominating set of permutation graphs ⋮ Dominating induced matching in some subclasses of bipartite graphs ⋮ Efficient edge domination in regular graphs ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ The Maximum Number of Dominating Induced Matchings ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ Dominating Induced Matchings ⋮ Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time ⋮ Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs ⋮ Exact algorithms for dominating induced matching based on graph partition ⋮ Maximal matchings in polyspiro and benzenoid chains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• A partial k-arboretum of graphs with bounded treewidth
• Efficient edge domination problems in graphs
• Parallel concepts in graph theory
• Combinatorial algorithms on a class of graphs
• Treewidth. Computations and approximations
• Algorithmic aspects of majority domination
• Weighted domination of cocomparability graphs
• Edge domination in graphs
• A linear algorithm for the domination number of a series-parallel graph
• A characterisation of rigid circuit graphs
• Weighted independent perfect domination on cocomparability graphs
• The weighted perfect domination problem and its variants
• Topology of series-parallel networks
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• Planar 3DM is NP-complete
• Graph minors. II. Algorithmic aspects of tree-width
• Scheduling Interval-Ordered Tasks
• Edge Dominating Sets in Graphs
• The Recognition of Series Parallel Digraphs
• Polynomially bounded algorithms for locatingp-centers on a tree
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS
• The edge domination problem

This page was built for publication: Perfect edge domination and efficient edge domination in graphs