Recognizing $P_4 $-Sparse Graphs in Linear Time

DOI10.1137/0221027zbMath0763.05093OpenAlexW1985562179MaRDI QIDQ3990660

Beverly Jamison, Stephan Olariu

Publication date: 28 June 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221027

zbMATH Keywords

cographslinear-time algorithmstree representationoptimal algorithmsrecognition algorithm\(P_ 4\)-sparse graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

Minimal separators in \(P_4\)-sparse graphs, The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs, BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES, Dot product dimensions of graphs, Linear time optimization algorithms for \(P_ 4\)-sparse graphs, On semi-\(P_ 4\)-sparse graphs, Scattering number and modular decomposition, Pairwise Compatibility Graphs: A Survey, Unnamed Item, Spiders and their kin: an investigation of Stanley's chromatic symmetric function for spiders and related graphs, From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats, On bipartite graphs with weak density of some subgraphs, A fast parallel algorithm to recognize P4-sparse graphs, On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs, On the structure of graphs with few \(P_4\)s, On the isomorphism of graphs with few P4s, Characterization and recognition of \(P_{4}\)-sparse graphs partitionable into \(k\) independent sets and \(\ell \) cliques, On variations of \(P_{4}\)-sparse graphs, The multiple domination and limited packing problems in graphs, Spiders can be recognized by counting their legs, Classes of perfect graphs, A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs, A survey of the algorithmic aspects of modular decomposition, Recognition and isomorphism of tree-like \(P_4\)-connected graphs, The parametric complexity of graph diameter augmentation, Maximization coloring problems on graphs with few \(P_4\), Path-bicolorable graphs, On the \(P_4\)-components of graphs, Progress on the description of identifying code polyhedra for some families of split graphs, Complexity and parameterized algorithms for cograph editing, Bandwidth and topological bandwidth of graphs with few \(P_4\)'s, Complexity of modification problems for reciprocal best match graphs, On the minimum sum coloring of \(P_4\)-sparse graphs, Best match graphs and reconciliation of gene trees with species trees, The graph sandwich problem for \(P_4\)-sparse graphs, Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes, Path-Bicolorable Graphs, Minimum Sum Coloring of P4-sparse graphs, Polynomial instances of the Packing Coloring Problem, On the b-coloring of cographs and \(P_{4}\)-sparse graphs, Efficient parallel recognition of cographs, ON GRAPHS WITH LIMITED NUMBER OF P₄-PARTNERS, ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S, On the \(b\)-dominating coloring of graphs, Generalized limited packings of some graphs with a limited number of \(P_4\)-partners, A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs