Induced matchings in asteroidal triple-free graphs

DOI10.1016/S0166-218X(03)00390-1zbMATH Open1029.05120OpenAlexW2020270928MaRDI QIDQ1414582FDOQ1414582

Authors 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

Asteroidal triple-free graphsBipartite permutation graphsIndependent setsChain graphsGreedy algorithmsInduced matchings

Mathematics Subject Classification ID

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

Recommendations

• Asteroidal Triple-Free Graphs
• Asteroidal triple-free graphs
• Independent Sets in Asteroidal Triple-Free Graphs
• Independent sets in asteroidal triple-free graphs
• Asteroidal-triple-free interval \(k\)-graphs
• Induced matchings in cubic graphs
• Induced matchings in intersection graphs
• On claw-free asteroidal triple-free graphs

Cites work

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

Cited in

(34)

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

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

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