A Linear Recognition Algorithm for Cographs
From MaRDI portal
Publication:3694709
DOI10.1137/0214065zbMath0575.68065OpenAlexW2015906942WikidataQ56474998 ScholiaQ56474998MaRDI QIDQ3694709
No author found.
Publication date: 1985
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0214065
chromatic numberisomorphismperfect graphslinear time algorithmHamiltonicitypermutation graphsexamination schedulingminimum fill-incotreeminimum weight dominationautomatic clustering of index termsclique determination
Related Items (only showing first 100 items - show all)
BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES ⋮ The pathwidth and treewidth of cographs ⋮ Parallel algorithm for cograph recognition with applications ⋮ Choosability of P 5-Free Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions ⋮ Edge Search Number of Cographs in Linear Time ⋮ P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs ⋮ Clique-perfectness and balancedness of some graph classes ⋮ Hadwiger Number of Graphs with Small Chordality ⋮ Contraction Blockers for Graphs with Forbidden Induced Paths ⋮ The Smallest Classes of Binary and Ternary Matroids Closed under Direct Sums and Complements ⋮ On the computational difficulty of the terminal connection problem ⋮ The Neighborhood Polynomial of Chordal Graphs ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Random cographs: Brownian graphon limit and asymptotic degree distribution ⋮ Graphs of Linear Clique-Width at Most 3 ⋮ Signed graphs with integral net Laplacian spectrum ⋮ On the isomorphism of graphs with few P4s ⋮ Characterizing and Computing Minimal Cograph Completions ⋮ The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs ⋮ Groups, Graphs, and Hypergraphs: Average Sizes of Kernels of Generic Matrices with Support Constraints ⋮ Complexity results on cosecure domination in graphs ⋮ Characterisations and Linear-Time Recognition of Probe Cographs ⋮ Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Computing and listing avoidable vertices and paths ⋮ New results on complementarity spectra of connected graphs ⋮ Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs ⋮ Cographs and 1-sums ⋮ Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs ⋮ Locating Eigenvalues of Symmetric Matrices - A Survey ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ Graphs with No Induced Five‐Vertex Path or Antipath ⋮ Unnamed Item ⋮ A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques ⋮ Precoloring Extension III: Classes of Perfect Graphs ⋮ Finding and counting small induced subgraphs efficiently ⋮ Dynamic Distance Hereditary Graphs Using Split Decomposition ⋮ LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P6-FREE GRAPHS ⋮ GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH ⋮ Shortest Paths between Shortest Paths and Independent Sets ⋮ Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures ⋮ -cospectrality and -energy in cographs ⋮ Acyclic polynomials of graphs ⋮ Unnamed Item ⋮ Pattern matching for permutations ⋮ Star Partitions of Perfect Graphs ⋮ A note on \(\alpha\)-redundant vertices in graphs ⋮ Partitioning a graph into complementary subgraphs ⋮ Detecting and Counting Small Pattern Graphs ⋮ On perfect switching classes ⋮ A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs ⋮ Strong triadic closure in cographs and graphs of low maximum degree ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized aspects of triangle enumeration ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ When can graph hyperbolicity be computed in linear time? ⋮ Fully dynamic algorithm for recognition and modular decomposition of permutation graphs ⋮ Secure total domination in chain graphs and cographs ⋮ Computing subset transversals in \(H\)-free graphs ⋮ The largest connected subgraph game ⋮ The largest connected subgraph game ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Rare siblings speed-up deterministic detection and counting of small pattern graphs ⋮ Parameterized complexity of diameter ⋮ Linear-time algorithm for the matched-domination problem in cographs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On perfect switching classes ⋮ Path-Bicolorable Graphs ⋮ Miscellaneous Digraph Classes ⋮ PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT ⋮ BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION ⋮ NLC2-DECOMPOSITION IN POLYNOMIAL TIME ⋮ A Combinatorial Algorithm to Optimally Colour the Edges of the Graphs That Are Join of Regular Graphs ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ Read-Once Functions Revisited and the Readability Number of a Boolean Function ⋮ Characterizations for co-graphs defined by restricted NLC-width or clique-width operations ⋮ Minimal separators in \(P_4\)-sparse graphs ⋮ A theorem on permutation graphs with applications ⋮ On the terminal connection problem ⋮ The neighborhood polynomial of chordal graphs ⋮ Pattern matching for permutations ⋮ Finding and counting small induced subgraphs efficiently ⋮ Recognizing cographs and threshold graphs through a classification of their edges ⋮ Generating and enumerating digitally convex sets of trees ⋮ Weighted independent sets in classes of \(P_6\)-free graphs ⋮ Efficient parallel recognition algorithms of cographs and distance hereditary graphs ⋮ On independent vertex sets in subclasses of apple-free graphs ⋮ Inapproximability of the lid-chromatic number ⋮ Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs ⋮ On the chromatic index of cographs and join graphs ⋮ Bi-complement reducible graphs ⋮ On semi-\(P_ 4\)-sparse graphs ⋮ Scattering number and modular decomposition ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese
This page was built for publication: A Linear Recognition Algorithm for Cographs
