A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements

DOI10.1016/J.IPL.2007.12.009MaRDI QIDQ963386zbMATH OpenOpenAlexFDO

Authors Frank Pok Man Chu

Publication date 19 April 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.12.009

zbMATH Keywords

algorithmsgraph algorithmscombinatorial problemslexicographic breadth first searchLBFSlexicographic BFSrecognizing trivially perfect graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Perfect graphs (05C17)

Recommendations

• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• A simple linear time LexBFS cograph recognition algorithm.
• A simple linear time algorithm for cograph recognition
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• scientific article; zbMATH DE number 1953107

Cites work

• scientific article; zbMATH DE number 4179413 (Why is no real title available?)
• scientific article; zbMATH DE number 3593613 (Why is no real title available?)
• A simple linear time LexBFS cograph recognition algorithm.
• Graph-Theoretic Concepts in Computer Science
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Quasi-threshold graphs
• The Comparability Graph of a Tree
• Trivially perfect graphs

Cited in

(11)

• Recognizing LBFS trees of bipartite graphs
• Linear optimization over homogeneous matrix cones
• Fast quasi-threshold editing
• Graph classes and forbidden patterns on three vertices
• Order consolidation for hierarchical product lines
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• Linearizing partial search orders
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• Monotonicity and expansion of global secure sets
• On the properties of weighted minimum colouring games

This page was built for publication: A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements

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