Efficient edge domination problems in graphs

DOI10.1016/0020-0190(93)90084-MzbMath0797.05076OpenAlexW2047747666MaRDI QIDQ1313728

Naveed A. Sherwani, Nancy D. Holmes, Dana L. Grinstead, Peter J. Slater

Publication date: 10 October 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90084-m

zbMATH Keywords

algorithmNP-completeseries-parallel graphline graphsedge domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (05C99)

Related Items (37)

Perfect edge domination and efficient edge domination in graphs ⋮ Perfect edge domination: hard and solvable cases ⋮ Efficient domination through eigenvalues ⋮ Kernelization of edge perfect code and its variants ⋮ THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS ⋮ Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time ⋮ Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs ⋮ Modelling and solving the perfect edge domination problem ⋮ Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs ⋮ On the dominating induced matching problem: spectral results and sharp bounds ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time ⋮ Linear-time algorithm for paired-domination on distance-hereditary graphs ⋮ On weighted efficient total domination ⋮ Maximum \(k\)-regular induced subgraphs ⋮ Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ Dominating induced matchings in graphs without a skew star ⋮ Dominating induced matchings for \(P_7\)-free graphs in linear time ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time ⋮ Stable-\(\Pi\) partitions of graphs ⋮ 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 ⋮ Complexity and kernels for bipartition into degree-bounded induced 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 ⋮ Solving the weighted efficient edge domination problem on bipartite permutation graphs ⋮ The Maximum Number of Dominating Induced Matchings ⋮ Dominating Induced Matchings ⋮ Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time ⋮ An overview of \((\kappa, \tau)\)-regular sets and their applications ⋮ Exact algorithms for dominating induced matching based on graph partition ⋮ Some results on dominating induced matchings

Cites Work

• A recurrence template for several parameters in series-parallel graphs
• Perfect codes in graphs
• Graph-theoretic parameters concerning domination, independence, and irredundance
• Towards a theory of domination in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficient edge domination problems in graphs