Treewidth and Pathwidth of Permutation Graphs
From MaRDI portal
Publication:4863978
DOI10.1137/S089548019223992XzbMath0840.05087OpenAlexW2091208300WikidataQ56560643 ScholiaQ56560643MaRDI QIDQ4863978
Dieter Kratsch, Ton Kloks, Hans L. Bodlaender
Publication date: 20 February 1996
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s089548019223992x
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (52)
A linear time algorithm to list the minimal separators of chordal graphs ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Treewidth of cocomparability graphs and a new order-theoretic parameter ⋮ Vertex ranking of asteroidal triple-free graphs ⋮ Computing directed pathwidth in \(O(1.89^n)\) time ⋮ On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators ⋮ Combining intensification and diversification strategies in VNS. An application to the vertex separation problem ⋮ Variable neighborhood search for the vertex separation problem ⋮ Measuring the vulnerability for classes of intersection graphs ⋮ Edge Search Number of Cographs in Linear Time ⋮ Pathwidth is NP-Hard for Weighted Trees ⋮ Treewidth for graphs with small chordality ⋮ Characterizations and algorithmic applications of chordal graph embeddings ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Constructive linear time algorithms for branchwidth ⋮ Recognizing interval digraphs and interval bigraphs in polynomial time ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ Two characterisations of the minimal triangulations of permutation graphs ⋮ Approximate search strategies for weighted trees ⋮ On treewidth and minimum fill-in of asteroidal triple-free graphs ⋮ The firebreak problem ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Mixed Search Number of Permutation Graphs ⋮ Edge search number of cographs ⋮ A Characterisation of the Minimal Triangulations of Permutation Graphs ⋮ The firefighter problem on graph classes ⋮ Approximating the treewidth of AT-free graphs. ⋮ Restricted vertex multicut on permutation graphs ⋮ Chordal embeddings of planar graphs ⋮ On the vertex ranking problem for trapezoid, circular-arc and other graphs ⋮ Computing \(K\)-terminal reliability of \(d\)-trapezoid graphs ⋮ A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs ⋮ How to compute digraph width measures on directed co-graphs ⋮ On the Maximum Weight Minimal Separator ⋮ A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs ⋮ Node-searching problem on block graphs ⋮ Locally definable vertex set properties are efficiently enumerable ⋮ How to use the minimal separators of a graph for its chordal triangulation ⋮ On probe permutation graphs ⋮ Computing branchwidth via efficient triangulations and blocks ⋮ Treewidth computations. II. Lower bounds ⋮ Treewidth and minimum fill-in on permutation graphs in linear time ⋮ On finding separators in temporal split and permutation graphs ⋮ On finding separators in temporal split and permutation graphs ⋮ On a property of minimal triangulations ⋮ Edge and node searching problems on trees ⋮ GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH ⋮ The first order definability of graphs with separators via the Ehrenfeucht game ⋮ On the maximum weight minimal separator ⋮ Linear rank-width and linear clique-width of trees ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
This page was built for publication: Treewidth and Pathwidth of Permutation Graphs
