A simple linear time algorithm for cograph recognition
From MaRDI portal
Publication:1764804
DOI10.1016/j.dam.2004.01.011zbMath1055.05107OpenAlexW2171760878WikidataQ56475004 ScholiaQ56475004MaRDI QIDQ1764804
Christophe Paul, Michel A. Habib
Publication date: 22 February 2005
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2004.01.011
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (44)
Linear-sized independent sets in random cographs and increasing subsequences in separable permutations ⋮ Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs ⋮ Unnamed Item ⋮ Structural parameterizations with modulator oblivion ⋮ Edge Search Number of Cographs in Linear Time ⋮ Complexity of edge monitoring on some graph classes ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ Hadwiger Number of Graphs with Small Chordality ⋮ Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs ⋮ Random cographs: Brownian graphon limit and asymptotic degree distribution ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ Groups, Graphs, and Hypergraphs: Average Sizes of Kernels of Generic Matrices with Support Constraints ⋮ Complexity results on cosecure domination in graphs ⋮ Edge search number of cographs ⋮ Probe Ptolemaic Graphs ⋮ Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs ⋮ Acyclic and star colorings of cographs ⋮ Unnamed Item ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ How to compute digraph width measures on directed co-graphs ⋮ A simple linear-time recognition algorithm for weakly quasi-threshold graphs ⋮ Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures ⋮ Finding a potential community in networks ⋮ Coupon coloring of cographs ⋮ -cospectrality and -energy in cographs ⋮ An improvement on the complexity of factoring read-once Boolean functions ⋮ Hybrid and generalized marked systems ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ On distance-preserving elimination orderings in graphs: complexity and algorithms ⋮ Eigenvalue location in cographs ⋮ Monotonicity and expansion of global secure sets ⋮ A new characterization of \(P_{6}\)-free graphs ⋮ Efficient algorithms for Roman domination on some classes of graphs ⋮ Characterizations of cographs as intersection graphs of paths on a grid ⋮ Reciprocal best match graphs ⋮ Defining and identifying cograph communities in complex networks ⋮ Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width ⋮ On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs ⋮ Counting Perfect Matchings and the Switch Chain ⋮ Linear-time algorithm for the matched-domination problem in cographs ⋮ BOUNDING THE NUMBER OF REDUCED TREES, COGRAPHS, AND SERIES-PARALLEL GRAPHS BY COMPRESSION ⋮ Twin-width and polynomial kernels ⋮ A Theoretical Framework for Instance Complexity of the Resource-Constrained Project Scheduling Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A tree representation for \(P_ 4\)-sparse graphs
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- On a property of the class of n-colorable graphs
- Efficient and Practical Algorithms for Sequential Modular Decomposition
- P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
- A New Class of Brittle Graphs
- A Linear Recognition Algorithm for Cographs
- Three Partition Refinement Algorithms
- PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
- Transitiv orientierbare Graphen
- Graph-Theoretic Concepts in Computer Science
- A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
This page was built for publication: A simple linear time algorithm for cograph recognition
