Solving NP-hard problems on \textsc{GaTEx} graphs: linear-time algorithms for perfect orderings, cliques, colorings, and independent sets
Cographs are a well-studied class of graphs on which many classical graph optimization problems, such as finding a maximum clique, maximum independent set or the chromatic number, may be solved by a linear-time algorithm. A graph is a cograph if it is either a single vertex or may be formed by taking the disjoint union or join of cographs. It is straightforward to see that a cograph may be described by a rooted tree in which the leaves correspond to vertices of the cograph and each non-leaf is labelled either \(0\) or \(1\) to describe either a disjoint union or a join of the subtrees of which it is the root.\N\NIn the present paper the authors construct algorithms running in time \(O(|V|+|E|)\) on \textsc{GaTEx} (galled-tree explainable) graphs, a class which strictly includes cographs. This class is derived from cographs by replacing the requirement that they are described by a rooted tree to being described by a directed galled tree. These are graphs obtained from trees in which some vertices have been `galled' or identified to create cycles in a restricted way. More precisely a \textit{galled tree} is a directed acyclic graph with a unique source in which every \(2\)-connected component of the underlying undirected graph is a cycle.\N\NThe authors give algorithms for \textsc{GaTEx} graphs to find a perfect order of the vertices (i.e., a total order which may be followed by a greedy algorithm to properly vertex colour every induced subgraph), and to determine an optimal proper vertex colouring, a maximum clique and a maximum independent set.
- A Linear Recognition Algorithm for Cographs
- A survey of the algorithmic aspects of modular decomposition
- Algorithmische Graphentheorie
- An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
- Beyond representing orthology relations by trees
- Cograph editing: Merging modules is equivalent to editing P₄s
- Complement reducible graphs
- Efficient and practical algorithms for sequential modular decomposition
- From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
- scientific article; zbMATH DE number 3891425 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Linear time algorithms for NP-hard problems restricted to \textsc{GaTEx} graphs
- Modular decomposition and transitive orientation
- On the complexity of recognizing perfectly orderable graphs
- Recovering symbolically dated, rooted trees from symbolic ultrametrics
- Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
- Theory of 2-structures. I: Clans, basic subclasses, and morphisms
- Theory of 2-structures. II: Representation through labeled tree families
This page was built for publication: Solving NP-hard problems on \textsc{GaTEx} graphs: linear-time algorithms for perfect orderings, cliques, colorings, and independent sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7002657)
