On Distance-3 Matchings and Induced Matchings
DOI10.1007/978-3-642-02029-2_11zbMath1194.05122OpenAlexW2155233937MaRDI QIDQ3655145
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
chordal graphsDistance-\(k\) matchingMaximum Distance-\(k\) Matching ProblemMaximum Induced Matching Problem
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Irredundancy in circular arc graphs
- On induced matchings
- Induced matchings in bipartite graphs
- Approximability results for the maximum and minimum maximal induced matching problems
- Maximum induced matchings for chordal graphs in linear time
- Decomposition by clique separators
- Problems and results in combinatorial analysis and graph theory
- NP-completeness of some generalizations of the maximum matching problem
- Induced matchings
- Modular decomposition and transitive orientation
- On linear and circular structure of (claw, net)-free graphs
- Induced matchings in asteroidal triple-free graphs
- Induced matchings in intersection 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
- On the approximability of the maximum induced matching problem
- Finding a maximum induced matching in weakly chordal graphs
- On maximum induced matchings in bipartite graphs
- New results on induced matchings
- On Hamiltonicity of \{claw, net\}-free graphs
- Linear Time Algorithms for Hamiltonian Problems on (Claw,Net)-Free Graphs
- Independent Domination in Triangle Graphs
- On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem
- Stability in circular arc graphs
- Graph Classes: A Survey
- Independent Sets in Asteroidal Triple-Free Graphs
- Bipartite Domination and Simultaneous Matroid Covers
- Induced matchings in cubic graphs
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Independent Sets of Maximum Weight in Apple-Free Graphs
This page was built for publication: On Distance-3 Matchings and Induced Matchings
