A Simple Linear Time LexBFS Cograph Recognition Algorithm

DOI10.1137/060664690zbMATH Open1187.05070OpenAlexW2000138132WikidataQ56474995 ScholiaQ56474995MaRDI QIDQ3648499FDOQ3648499

Derek G. Corneil, Christophe Paul, M. A. Habib, Anna Bretscher

Publication date: 27 November 2009

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/d516570b66422d2cf0e121e65db3f938668380c3

Recommendations

• A simple linear time LexBFS cograph recognition algorithm.
• A simple linear time algorithm for cograph recognition
• scientific article; zbMATH DE number 3896983
• A Linear Recognition Algorithm for Cographs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing

zbMATH Keywords

graph algorithmmodular decompositionlinear time algorithmLexBFS\(P_4\)-free graphscograph recognition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Cited In (25)

• Recognizing LBFS trees of bipartite graphs
• A Linear Recognition Algorithm for Cographs
• Cograph editing: Merging modules is equivalent to editing P_4s
• A general label search to investigate classical graph search algorithms
• Miscellaneous Digraph Classes
• Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs
• Linearizing partial search orders
• Dominating induced matchings for \(P_7\)-free graphs in linear time
• Characterizations of cographs as intersection graphs of paths on a grid
• Graphon convergence of random cographs
• A survey of the algorithmic aspects of modular decomposition
• Defining and identifying cograph communities in complex networks
• Reciprocal best match graphs
• Parameterized complexity of diameter
• A new LBFS-based algorithm for cocomparability graph recognition
• A linear algorithm for obtaining the Laplacian eigenvalues of a cograph
• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
• The structural complexity landscape of finding balance-fair shortest paths
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• A simple linear time algorithm for cograph recognition
• A simple linear-time recognition algorithm for weakly quasi-threshold graphs
• Random cographs: Brownian graphon limit and asymptotic degree distribution
• Groups, Graphs, and Hypergraphs: Average Sizes of Kernels of Generic Matrices with Support Constraints
• Parameterized aspects of triangle enumeration
• Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition

This page was built for publication: A Simple Linear Time LexBFS Cograph Recognition Algorithm

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