Dominating induced matchings for P₇-free graphs in linear time
DOI10.1007/S00453-012-9709-4zbMATH Open1307.05171OpenAlexW2444140751MaRDI QIDQ476446FDOQ476446
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
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
linear time algorithmdominating induced matchingrobust algorithm\(P_7\)-free graphsefficient edge domination
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)
Cites Work
- Title not available (Why is that?)
- Modular decomposition and transitive orientation
- Efficient graph representations
- Linear time solvable optimization problems on graphs of bounded clique-width
- On the clique-width of some perfect graph classes
- Distance-hereditary graphs
- A Linear Recognition Algorithm for Cographs
- On algorithms for (\(P_5\), gem)-free graphs
- Efficient edge domination problems in graphs
- Perfect edge domination and efficient edge domination in graphs
- Efficient edge domination on hole-free graphs in polynomial time
- Dominating induced matchings
- Efficient dominating and edge dominating sets for graphs and hypergraphs
- On the complexity of the dominating induced matching problem in hereditary classes of graphs
- A Simple Linear Time LexBFS Cograph Recognition Algorithm
- On the structure of (\(P_{5}\),\,gem)-free graphs
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
Cited In (19)
- Combinatorial and spectral properties of König-Egerváry graphs
- Independent feedback vertex set for \(P_5\)-free graphs
- Some results on dominating induced matchings
- Dominating induced matchings for \(P _{7}\)-free graphs in linear time
- \(O(n)\) time algorithms for dominating induced matching problems
- Dominating induced matchings in graphs without a skew star
- Efficient domination through eigenvalues
- Graphs with maximal induced matchings of the same size
- Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time
- Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
- Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time
- Modelling and solving the perfect edge domination problem
- 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
- Graphs whose vertices of degree at least 2 lie in a triangle
- Fast algorithms for some dominating induced matching problems
- Exact algorithms for dominating induced matching based on graph partition
- Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs
- Finding dominating induced matchings in \(P_8\)-free graphs in polynomial 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)
