(\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.

DOI10.1016/S0166-218X(03)00266-XzbMath1175.90395MaRDI QIDQ1428548

Andreas Brandstädt

Publication date: 29 March 2004

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

zbMATH Keywords

graphs; Clique width of graphs; Problem; Prime; (\(P_5\)diamond)-free graphs; Maximum Weight Clique Problem; Maximum Weight Stable Set; Modules and homogeneous sets in graphs

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Weighted independent sets in classes of \(P_6\)-free graphs, On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem, Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences, Maximum weight independent sets in odd-hole-free graphs without dart or without bull, On minimal prime extensions of a four-vertex graph in a prime graph, New applications of clique separator decomposition for the maximum weight stable set problem, On indicated coloring of graphs, First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs, Colouring of \((P_3 \cup P_2)\)-free graphs, Independent sets in extensions of 2\(K_{2}\)-free graphs, Two forbidden induced subgraphs and well-quasi-ordering, Sandwiches missing two ingredients of order four, Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes, Triangle packings and transversals of some \(K_{4}\)-free graphs, Counting spanning trees using modular decomposition, Bounding the Clique-Width of H-free Chordal Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of generalized clique packing
• Distance-hereditary graphs
• Complement reducible graphs
• Trivially perfect graphs
• Modular decomposition and transitive orientation
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• The Complexity of the Partial Order Dimension Problem
• A Linear Recognition Algorithm for Cographs
• Some classes of perfectly orderable graphs
• The Comparability Graph of a Tree
• Graph Classes: A Survey
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Difference graphs