Linear time optimization algorithms for \(P_ 4\)-sparse graphs

DOI10.1016/0166-218X(94)00012-3zbMath0831.68075OpenAlexW59383121WikidataQ126459170 ScholiaQ126459170MaRDI QIDQ1897361

Stephan Olariu, Beverly Jamison

Publication date: 6 February 1996

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

Full work available at URL: https://doi.org/10.1016/0166-218x(94)00012-3

zbMATH Keywords

NP-hard problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (21)

Minimal separators in \(P_4\)-sparse graphs ⋮ Hierarchical and modularly-minimal vertex colorings ⋮ Bi-complement reducible graphs ⋮ On some domination colorings of graphs ⋮ Unnamed Item ⋮ A fast parallel algorithm to recognize P4-sparse graphs ⋮ On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs ⋮ On the \(b\)-continuity of the lexicographic product of graphs ⋮ On the hull number on cycle convexity of graphs ⋮ Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques ⋮ On variations of \(P_{4}\)-sparse graphs ⋮ Recognition and isomorphism of tree-like \(P_4\)-connected graphs ⋮ Graphs with small fall-spectrum ⋮ Maximization coloring problems on graphs with few \(P_4\) ⋮ Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ Bandwidth and topological bandwidth of graphs with few \(P_4\)'s ⋮ Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes ⋮ Triangulating graphs with few \(P_4\)'s ⋮ The clique operator on cographs and serial graphs ⋮ On the b-coloring of cographs and \(P_{4}\)-sparse graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weak bipolarizable graphs
• Complement reducible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• On a class of posets and the corresponding comparability graphs
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A Linear Recognition Algorithm for Cographs
• The edge inducibility of graphs
• Computing the Minimum Fill-In is NP-Complete
• Recognizing $P_4 $-Sparse Graphs in Linear Time

This page was built for publication: Linear time optimization algorithms for \(P_ 4\)-sparse graphs