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

DOI10.1016/j.ipl.2007.12.009zbMath1185.05134OpenAlexW2089241552MaRDI QIDQ963386

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

algorithmscombinatorial problemsgraph algorithmslexicographic breadth first searchLBFSlexicographic BFSrecognizing trivially perfect graphs

Mathematics Subject Classification ID

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

Related Items (9)

Fast Quasi-Threshold Editing ⋮ Linearizing partial search orders ⋮ Linear optimization over homogeneous matrix cones ⋮ Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs ⋮ Monotonicity and expansion of global secure sets ⋮ Order consolidation for hierarchical product lines ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ On the properties of weighted minimum colouring games

Cites Work

• Unnamed Item
• Unnamed Item
• Trivially perfect graphs
• 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
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science

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