On distance-3 matchings and induced matchings

DOI10.1007/978-3-642-02029-2_11MaRDI QIDQ3655145zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Raffaele Mosca

Publication date 7 January 2010

Published in Graph Theory, Computational Intelligence and Thought (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02029-2_11

zbMATH Keywords

chordal graphsDistance-\(k\) matchingMaximum Distance-\(k\) Matching ProblemMaximum Induced Matching Problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On distance-3 matchings and induced matchings
• New min-max theorems for weakly chordal and dually chordal graphs
• On minimum maximal distance-\(k\) matchings
• On minimum maximal distance-\(k\) matchings
• Induced matchings

Cites work

• scientific article; zbMATH DE number 434499 (Why is no real title available?)
• scientific article; zbMATH DE number 3889566 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 3908479 (Why is no real title available?)
• scientific article; zbMATH DE number 1496857 (Why is no real title available?)
• scientific article; zbMATH DE number 2191988 (Why is no real title available?)
• Approximability results for the maximum and minimum maximal induced matching problems
• Bipartite Domination and Simultaneous Matroid Covers
• Decomposition by clique separators
• Finding a maximum induced matching in weakly chordal graphs
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• Graph Classes: A Survey
• Independent Domination in Triangle Graphs
• Independent Sets in Asteroidal Triple-Free Graphs
• Independent Sets of Maximum Weight in Apple-Free Graphs
• Induced matchings
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in bipartite graphs
• Induced matchings in cubic graphs
• Induced matchings in intersection graphs.
• Irredundancy in circular arc graphs
• Linear time algorithms for Hamiltonian problems on (claw, net)-free graphs
• Maximum induced matchings for chordal graphs in linear time
• Modular decomposition and transitive orientation
• NP-completeness of some generalizations of the maximum matching problem
• New results on induced matchings
• On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem
• On Hamiltonicity of \{claw, net\}-free graphs
• On induced matchings
• On linear and circular structure of (claw, net)-free graphs
• On maximum induced matchings in bipartite graphs
• On the approximability of the maximum induced matching problem
• On the clique-width of some perfect graph classes
• Problems and results in combinatorial analysis and graph theory
• Stability in circular arc graphs
• The structure of claw-free graphs

Cited in

(5)

• New min-max theorems for weakly chordal and dually chordal graphs
• On minimum maximal distance-\(k\) matchings
• On distance-3 matchings and induced matchings
• On minimum maximal distance-\(k\) matchings
• Distance-\(d\) independent set problems for bipartite and chordal graphs

This page was built for publication: On distance-3 matchings and induced matchings

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