Dominating induced matchings for P₇-free graphs in linear time

DOI10.1007/S00453-012-9709-4MaRDI QIDQ476446zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Raffaele Mosca

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

zbMATH Keywords

linear time algorithmdominating induced matchingrobust algorithm\(P_7\)-free graphsefficient edge domination

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Dominating induced matchings for \(P _{7}\)-free graphs in linear time
• Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
• Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
• Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time
• Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
• Distance-hereditary graphs
• Dominating induced matchings
• Efficient dominating and edge dominating sets for graphs and hypergraphs
• Efficient edge domination on hole-free graphs in polynomial time
• Efficient edge domination problems in graphs
• Efficient graph representations
• Linear time solvable optimization problems on graphs of bounded clique-width
• Modular decomposition and transitive orientation
• On algorithms for (\(P_5\), gem)-free graphs
• On the clique-width of some perfect graph classes
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• On the structure of (\(P_{5}\),\,gem)-free graphs
• Perfect edge domination and efficient edge domination in graphs

Cited in

(19)

• Exact algorithms for dominating induced matching based on graph partition
• Fast algorithms for some dominating induced matching problems
• Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time
• Some results on dominating induced matchings
• Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time
• On the dominating induced matching problem: spectral results and sharp bounds
• Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time
• \(O(n)\) time algorithms for dominating induced matching problems
• Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
• Dominating induced matchings in graphs without a skew star
• Modelling and solving the perfect edge domination problem
• Combinatorial and spectral properties of König-Egerváry graphs
• Efficient domination through eigenvalues
• Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs
• Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
• Independent feedback vertex set for \(P_5\)-free graphs
• Graphs with maximal induced matchings of the same size
• Graphs whose vertices of degree at least 2 lie in a triangle
• Dominating induced matchings for \(P _{7}\)-free graphs in linear time

This page was built for publication: Dominating induced matchings for \(P_7\)-free graphs in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476446)