Induced matchings in asteroidal triple-free graphs

DOI10.1016/S0166-218X(03)00390-1zbMath1029.05120OpenAlexW2020270928MaRDI QIDQ1414582

Jou-Ming Chang

Publication date: 4 December 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00390-1

zbMATH Keywords

Bipartite permutation graphsAsteroidal triple-free graphsIndependent setsChain graphsGreedy algorithmsInduced matchings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (32)

Unnamed Item ⋮ Graphs with maximal induced matchings of the same size ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Unnamed Item ⋮ On orthogonal ray trees ⋮ A min-max property of chordal bipartite graphs with applications ⋮ Induced matchings in intersection graphs. ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ Approximating weighted induced matchings ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ Induced Matchings in Graphs of Degree at Most 4 ⋮ On the approximability of the maximum induced matching problem ⋮ On distance-3 matchings and induced matchings ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ The complexity of dissociation set problems in graphs ⋮ The induced separation dimension of a graph ⋮ The induced matching and chain subgraph cover problems for convex bipartite graphs ⋮ Equality of distance packing numbers ⋮ Finding a maximum induced matching in weakly chordal graphs ⋮ Maximum induced matchings for chordal graphs in linear time ⋮ Maximum induced matching problem on hhd-free graphs ⋮ On Distance-3 Matchings and Induced Matchings ⋮ Recent progress on strong edge-coloring of graphs ⋮ Brambles and independent packings in chordal graphs ⋮ The graphs with maximum induced matching and maximum matching the same size ⋮ Independent packings in structured graphs ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs ⋮ Moderately exponential time algorithms for the maximum induced matching problem ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Irredundancy in circular arc graphs
• Bipartite permutation graphs
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• On the complexity of the k-chain subgraph cover problem
• Characterizations and algorithmic applications of chordal graph embeddings
• On the powers of graphs with bounded asteroidal number
• On claw-free asteroidal triple-free graphs
• Optimizing weakly triangulated graphs
• On the semi-perfect elimination
• New results on induced matchings
• Linear Time Algorithms for Hamiltonian Problems on (Claw,Net)-Free Graphs
• Representation of a finite graph by a set of intervals on the real line
• The Complexity of the Partial Order Dimension Problem
• Representations of chordal graphs as subtrees of a tree
• Covering the edges with consecutive sets
• Graph Classes: A Survey
• Independent Sets in Asteroidal Triple-Free Graphs
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• On the 2-Chain Subgraph Cover and Related Problems
• Asteroidal Triple-Free Graphs
• Transitiv orientierbare Graphen
• Difference graphs
• On the structure of graphs with bounded asteroidal number

This page was built for publication: Induced matchings in asteroidal triple-free graphs