Dominating Induced Matchings for P 7-free Graphs in Linear Time

DOI10.1007/978-3-642-25591-5_12zbMath1349.05249OpenAlexW2030013015MaRDI QIDQ3104604

Raffaele Mosca, Andreas Brandstädt

Publication date: 16 December 2011

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-25591-5_12

zbMATH Keywords

robust algorithmdominating induced matchinglinear-time algorithmefficient edge domination\(P _{7}\)-free graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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 (5)

Perfect edge domination: hard and solvable cases ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ Fast algorithms for some dominating induced matching problems ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ The Maximum Number of Dominating Induced Matchings

This page was built for publication: Dominating Induced Matchings for P 7-free Graphs in Linear Time