Linear time optimization algorithms for P_ 4-sparse graphs

DOI10.1016/0166-218X(94)00012-3MaRDI QIDQ1897361zbMATH OpenOpenAlexWikidataFDO

Authors Beverly Jamison, Stephan Olariu

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)

Recommendations

• Recognizing P₄ -Sparse Graphs in Linear Time
• On semi-\(P_ 4\)-sparse graphs
• A tree representation for \(P_ 4\)-sparse graphs
• On variations of \(P_{4}\)-sparse graphs
• On extended P₄-reducible and extended P₄-sparse graphs

Cites work

• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A Linear Recognition Algorithm for Cographs
• A tree representation for \(P_ 4\)-sparse graphs
• Complement reducible graphs
• Computing the Minimum Fill-In is NP-Complete
• Graph theory
• scientific article; zbMATH DE number 67616 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On a class of posets and the corresponding comparability graphs
• Recognizing P₄ -Sparse Graphs in Linear Time
• The edge inducibility of graphs
• Weak bipolarizable graphs

Cited in

(35)

• The graph sandwich problem for P₄-sparse graphs
• Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
• On the b-coloring of cographs and \(P_{4}\)-sparse graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Triangulating graphs with few \(P_4\)'s
• Bi-complement reducible graphs
• On semi-\(P_ 4\)-sparse graphs
• A fast parallel algorithm to recognize P4-sparse graphs
• On extended P₄-reducible and extended P₄-sparse graphs
• On variations of \(P_{4}\)-sparse graphs
• On the \(b\)-continuity of the lexicographic product of graphs
• Graphs with small fall-spectrum
• Hamiltonicity in graphs with few \(P_ 4\)'s
• The clique operator on cographs and serial graphs
• Recognition and isomorphism of tree-like \(P_4\)-connected graphs
• On some domination colorings of graphs
• Maximization coloring problems on graphs with few \(P_4\)
• SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s
• scientific article; zbMATH DE number 5120879 (Why is no real title available?)
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• Recognizing P₄ -Sparse Graphs in Linear Time
• scientific article; zbMATH DE number 1282854 (Why is no real title available?)
• Hierarchical and modularly-minimal vertex colorings
• On graphs with limited number of \(P_{4}\)-partners
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Efficient algorithms for graphs with few P₄'s
• Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
• On the hull number on cycle convexity of graphs
• scientific article; zbMATH DE number 7740902 (Why is no real title available?)
• Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques
• Acyclic and star coloring of \(P_4\)-reducible and \(P_4\)-sparse graphs
• On the rank and the general position number in cycle convexity
• Minimal separators in \(P_4\)-sparse graphs
• An optimal parallel solution for the path cover problem on \(P_{4}\)-sparse graphs

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

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