(\(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)
graphsClique width of graphsProblemPrime(\(P_5\)diamond)-free graphsMaximum Weight Clique ProblemMaximum Weight Stable SetModules and homogeneous sets in graphs
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (17)
Weighted independent sets in classes of \(P_6\)-free graphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ Triangle packings and transversals of some \(K_{4}\)-free graphs ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences ⋮ On indicated coloring of graphs ⋮ Colouring of \((P_3 \cup P_2)\)-free graphs ⋮ Counting spanning trees using modular decomposition ⋮ Maximum weight independent sets in odd-hole-free graphs without dart or without bull ⋮ First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ On minimal prime extensions of a four-vertex graph in a prime graph ⋮ Two forbidden induced subgraphs and well-quasi-ordering ⋮ Sandwiches missing two ingredients of order four ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds ⋮ Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
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
This page was built for publication: (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
