Perfect edge domination: hard and solvable cases

DOI10.1007/s10479-017-2664-3zbMath1388.05139arXiv1705.08379MaRDI QIDQ1639290

Veronica A. Moyano, Min Chih Lin, Jayme Luiz Szwarcfiter, Vadim V. Lozin

Publication date: 12 June 2018

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.08379

zbMATH Keywords

NP-completeness; cubic graphs; claw-free graphs; complexity dichotomy; perfect edge domination

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C22: Signed and weighted graphs

Related Items

Modelling and solving the perfect edge domination problem

Cites Work

• Unnamed Item
• Efficient and perfect domination on circular-arc graphs
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Efficient edge domination in regular graphs
• Dominating cliques in \(P_ 5\)-free graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Efficient edge domination problems in graphs
• Perfect edge domination and efficient edge domination in graphs
• Fast algorithms for some dominating induced matching problems
• Exact algorithms for dominating induced matching based on graph partition
• An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching
• A New Characterization of $$P_k$$-free Graphs
• Dominating Induced Matchings for P 7-free Graphs in Linear Time
• Dominating induced matchings in graphs containing no long claw
• Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
• The Maximum Number of Dominating Induced Matchings