Dominating induced matchings for \(P_7\)-free graphs in linear time
DOI10.1007/s00453-012-9709-4zbMath1307.05171OpenAlexW2444140751MaRDI QIDQ476446
Raffaele Mosca, Andreas Brandstädt
Publication date: 2 December 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9709-4
linear time algorithmrobust algorithmdominating induced matching\(P_7\)-free graphsefficient edge domination
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (15)
Cites Work
- Unnamed Item
- On the complexity of the dominating induced matching problem in hereditary classes of graphs
- On algorithms for (\(P_5\), gem)-free graphs
- Distance-hereditary graphs
- Modular decomposition and transitive orientation
- Efficient edge domination problems in graphs
- Efficient graph representations
- Perfect edge domination and efficient edge domination in graphs
- On the structure of (\(P_{5}\),\,gem)-free graphs
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- Linear time solvable optimization problems on graphs of bounded clique-width
- Efficient Edge Domination on Hole-Free Graphs in Polynomial Time
- A Simple Linear Time LexBFS Cograph Recognition Algorithm
- Dominating Induced Matchings
- A Linear Recognition Algorithm for Cographs
- Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
This page was built for publication: Dominating induced matchings for \(P_7\)-free graphs in linear time