(P₅, diamond)-free graphs revisited: Structure and linear time optimization.

DOI10.1016/S0166-218X(03)00266-XMaRDI QIDQ1428548zbMATH OpenFDO

Authors Andreas Brandstädt

Publication date 29 March 2004

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

zbMATH Keywords

graphsClique width of graphsProblem(\(P_5\)diamond)-free graphsMaximum Weight Clique ProblemMaximum Weight Stable SetModules and homogeneous sets in graphsPrime

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• On algorithms for (P₅, gem)-free graphs
• Fundamentals of Computation Theory
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• On (\(P_{5}\), diamond)-free graphs
• On the structure of (\(P_{5}\),\,gem)-free graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3896983 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• Complement reducible graphs
• Difference graphs
• Distance-hereditary graphs
• Efficient and practical algorithms for sequential modular decomposition
• Graph Classes: A Survey
• Handle-rewriting hypergraph grammars
• Linear time solvable optimization problems on graphs of bounded clique-width
• Modular decomposition and transitive orientation
• On the clique-width of some perfect graph classes
• Some classes of perfectly orderable graphs
• The Comparability Graph of a Tree
• The Complexity of the Partial Order Dimension Problem
• The complexity of generalized clique packing
• Trivially perfect graphs
• Upper bounds to the clique width of graphs

Cited in

(22)

• Optimization and Recognition for K 5-minor Free Graphs in Linear Time
• 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
• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
• Colouring of (P₃ P₂)-free graphs
• On the structure of (\(P_{5}\),\,gem)-free graphs
• 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
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• On algorithms for (P₅, gem)-free graphs
• New applications of clique separator decomposition for the maximum weight stable set problem
• On (\(P_{5}\), diamond)-free graphs
• On indicated coloring of graphs
• On minimal prime extensions of a four-vertex graph in a prime graph
• Sandwiches missing two ingredients of order four
• Triangle packings and transversals of some \(K_{4}\)-free graphs
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• Bounding the clique-width of \(H\)-free chordal graphs
• Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
• Counting spanning trees using modular decomposition
• Fundamentals of Computation Theory

This page was built for publication: (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.

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