A Simple Linear Time LexBFS Cograph Recognition Algorithm
From MaRDI portal
Publication:3648499
DOI10.1137/060664690zbMath1187.05070OpenAlexW2000138132WikidataQ56474995 ScholiaQ56474995MaRDI QIDQ3648499
Christophe Paul, Anna Bretscher, Derek Gordon Corneil, Michel A. Habib
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
graph algorithmlinear time algorithmmodular decompositionLexBFS\(P_4\)-free graphscograph recognition
Related Items (21)
Linear-sized independent sets in random cographs and increasing subsequences in separable permutations ⋮ A new LBFS-based algorithm for cocomparability graph recognition ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Linearizing partial search orders ⋮ A general label search to investigate classical graph search algorithms ⋮ The structural complexity landscape of finding balance-fair shortest paths ⋮ Graphon convergence of random cographs ⋮ Random cographs: Brownian graphon limit and asymptotic degree distribution ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ Groups, Graphs, and Hypergraphs: Average Sizes of Kernels of Generic Matrices with Support Constraints ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Dominating induced matchings for \(P_7\)-free graphs in linear time ⋮ A simple linear-time recognition algorithm for weakly quasi-threshold graphs ⋮ Parameterized aspects of triangle enumeration ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ Characterizations of cographs as intersection graphs of paths on a grid ⋮ Reciprocal best match graphs ⋮ Parameterized complexity of diameter ⋮ Defining and identifying cograph communities in complex networks ⋮ Miscellaneous Digraph Classes
This page was built for publication: A Simple Linear Time LexBFS Cograph Recognition Algorithm
