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

DOI10.1016/J.IPL.2007.12.009zbMATH Open1185.05134OpenAlexW2089241552MaRDI QIDQ963386FDOQ963386

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

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

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)

Cites Work

• Trivially perfect graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• The Comparability Graph of a Tree
• Quasi-threshold graphs
• A simple linear time LexBFS cograph recognition algorithm.
• Graph-Theoretic Concepts in Computer Science
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (11)

• Recognizing LBFS trees of bipartite graphs
• Linear optimization over homogeneous matrix cones
• Graph classes and forbidden patterns on three vertices
• Fast quasi-threshold editing
• 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)