(\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
From MaRDI portal
Publication:1428548
DOI10.1016/S0166-218X(03)00266-XzbMath1175.90395MaRDI QIDQ1428548
Publication date: 29 March 2004
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
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
Related Items
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, 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, First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs, Independent sets in extensions of 2\(K_{2}\)-free graphs, Two forbidden induced subgraphs and well-quasi-ordering, Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes, Counting spanning trees using modular decomposition
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
