On linear and circular structure of (claw, net)-free graphs

DOI10.1016/S0166-218X(02)00571-1zbMath1032.05095OpenAlexW1983733602MaRDI QIDQ1406025

Feodor F. Dragan, Andreas Brandstädt

Publication date: 9 September 2003

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

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

zbMATH Keywords

stability numberlinear-time algorithmindependent dominationlinear structuredominating cyclecircular structure(claw, net)-free graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (17)

On independent vertex sets in subclasses of apple-free graphs ⋮ The computational complexity of dominating set problems for instances with bounded minors of constraint matrices ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Minimum weighted clique cover on claw‐free perfect graphs ⋮ Tree-Width and Optimization in Bounded Degree Graphs ⋮ Proper interval vertex deletion ⋮ Unnamed Item ⋮ Dominating and large induced trees in regular graphs ⋮ On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem ⋮ An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\) ⋮ On distance-3 matchings and induced matchings ⋮ Proper Interval Vertex Deletion ⋮ On the power of BFS to determine a graph's diameter ⋮ Clique-perfectness of complements of line graphs ⋮ On Distance-3 Matchings and Induced Matchings ⋮ Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition ⋮ The computational complexity of three graph problems for instances with bounded minors of constraint matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time algorithm to compute a dominating path in an AT-free graph
• On domination and independent domination numbers of a graph
• Tolerance graphs
• The struction of a graph: Application to CN-free graphs
• Trapezoid graphs and their coloring
• On maximal independent sets of vertices in claw-free graphs
• Hamiltonicity in claw-free graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• LexBFS-orderings and powers of chordal graphs
• On claw-free asteroidal triple-free graphs
• On the semi-perfect elimination
• Matrix characterizations of circular-arc graphs
• Linear Time Algorithms for Hamiltonian Problems on (Claw,Net)-Free Graphs
• Domination on Cocomparability Graphs
• Representation of a finite graph by a set of intervals on the real line
• Edge Dominating Sets in Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Graph Classes: A Survey
• Independent Sets in Asteroidal Triple-Free Graphs
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Asteroidal Triple-Free Graphs
• Characterizing circular-arc graphs
• Partial orders of dimension 2
• Permutation Graphs and Transitive Graphs

This page was built for publication: On linear and circular structure of (claw, net)-free graphs