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
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
