The Pathwidth and Treewidth of Cographs
From MaRDI portal
Publication:4695381
DOI10.1137/0406014zbMath0773.05091OpenAlexW2012154006MaRDI QIDQ4695381
Rolf H. Möhring, Hans L. Bodlaender
Publication date: 21 July 1993
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://dspace.library.uu.nl/handle/1874/16625
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (69)
A vertex incremental approach for maintaining chordality ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Bounding the search number of graph products ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Treewidth of cocomparability graphs and a new order-theoretic parameter ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Computing directed pathwidth in \(O(1.89^n)\) time ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs ⋮ Edge Search Number of Cographs in Linear Time ⋮ Treewidth for graphs with small chordality ⋮ Characterizations and algorithmic applications of chordal graph embeddings ⋮ Triangulating graphs without asteroidal triples ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ On interval routing schemes and treewidth ⋮ Two characterisations of the minimal triangulations of permutation graphs ⋮ Contraction Blockers for Graphs with Forbidden Induced Paths ⋮ Fugitive-search games on graphs and related parameters ⋮ Triangulating multitolerance graphs ⋮ Principled deep neural network training through linear programming ⋮ Weighted maximum-clique transversal sets of graphs ⋮ On Interval Routing Schemes and treewidth ⋮ Edge search number of cographs ⋮ A Characterisation of the Minimal Triangulations of Permutation Graphs ⋮ How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Tree-width and path-width of comparability graphs of interval orders ⋮ Automata-based Representations for Infinite Graphs ⋮ Inference and Learning in Multi-dimensional Bayesian Network Classifiers ⋮ Acyclic and star colorings of cographs ⋮ A revisit of the scheme for computing treewidth and minimum fill-in ⋮ How to compute digraph width measures on directed co-graphs ⋮ The complexity of minimum-length path decompositions ⋮ Node-searching problem on block graphs ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ The complexity of subgraph isomorphism for classes of partial k-trees ⋮ Neighbourhood-width of trees ⋮ Comparing the metric and strong dimensions of graphs ⋮ How to use the minimal separators of a graph for its chordal triangulation ⋮ Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization ⋮ Fugitive-search games on graphs and related parameters ⋮ Treewidth computations. I: Upper bounds ⋮ Tree decompositions with small cost ⋮ Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width ⋮ Dynamic programming and planarity: improved tree-decomposition based algorithms ⋮ Treewidth and minimum fill-in on permutation graphs in linear time ⋮ On characterizations for subclasses of directed co-graphs ⋮ Linear layouts measuring neighbourhoods in graphs ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ Tree-decompositions of small pathwidth ⋮ On intervalizing \(k\)-colored graphs for DNA physical mapping ⋮ Exclusive graph searching vs. pathwidth ⋮ Computing subset transversals in \(H\)-free graphs ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ An optimal parallel algorithm for node ranking of cographs ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ FPT is characterized by useful obstruction sets ⋮ Linear-time algorithm for the matched-domination problem in cographs ⋮ Triangulating graphs with few \(P_4\)'s ⋮ Partial and perfect path covers of cographs ⋮ Edge and node searching problems on trees ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ Efficient parallel recognition of cographs ⋮ On perfect and quasiperfect dominations in graphs ⋮ Tree decompositions and social graphs ⋮ On the spectrum and number of convex sets in graphs ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
This page was built for publication: The Pathwidth and Treewidth of Cographs
