Treewidth and Pathwidth of Permutation Graphs

DOI10.1137/S089548019223992XMaRDI QIDQ4863978zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ton Kloks, Dieter Kratsch, 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

zbMATH Keywords

algorithmtreewidthtriangulationpathwidthinterval graphchordal graphpermutation graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Parallel algorithms in computer science (68W10)

Recommendations

• Treewidth and pathwidth of permutation graphs
• Treewidth and minimum fill-in on permutation graphs in linear time
• Graph-Theoretic Concepts in Computer Science
• The pathwidth and treewidth of cographs
• The Pathwidth and Treewidth of Cographs
• scientific article; zbMATH DE number 3855165
• scientific article; zbMATH DE number 1109395
• Tree-width and circumference of graphs
• scientific article; zbMATH DE number 772777
• scientific article; zbMATH DE number 1868528

Cited in

(55)

• Pathwidth is NP-Hard for Weighted Trees
• A linear time algorithm to list the minimal separators of chordal graphs
• Locally definable vertex set properties are efficiently enumerable
• A Characterisation of the Minimal Triangulations of Permutation Graphs
• How to use the minimal separators of a graph for its chordal triangulation
• Treewidth and minimum fill-in on permutation graphs in linear time
• 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
• On a property of minimal triangulations
• Treewidth computations. II. Lower bounds
• On probe permutation graphs
• Approximating the treewidth of AT-free graphs.
• Edge search number of cographs
• Constructive linear time algorithms for branchwidth
• Edge Search Number of Cographs in Linear Time
• Characterizations and algorithmic applications of chordal graph embeddings
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Treewidth for graphs with small chordality
• Vertex ranking of asteroidal triple-free graphs
• Computing directed pathwidth in O(1.89ⁿ) time
• Chordal embeddings of planar graphs
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Computing branchwidth via efficient triangulations and blocks
• Approximate search strategies for weighted trees
• Restricted vertex multicut on permutation graphs
• On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
• Edge and node searching problems on trees
• Linear rank-width and linear clique-width of trees
• On finding separators in temporal split and permutation graphs
• On finding separators in temporal split and permutation graphs
• The firebreak problem
• On the maximum weight minimal separator
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Measuring the vulnerability for classes of intersection graphs
• The firefighter problem on graph classes
• Finding a maximum minimal separator: graph classes and fixed-parameter tractability
• Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
• Variable neighborhood search for the vertex separation problem
• A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs
• Node-searching problem on block graphs
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
• How to compute digraph width measures on directed co-graphs
• On the maximum weight minimal separator
• The first order definability of graphs with separators via the Ehrenfeucht game
• Treewidth and pathwidth of permutation graphs
• Graph-Theoretic Concepts in Computer Science
• Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• As Time Goes By: Reflections on Treewidth for Temporal Graphs
• Large Induced Subgraphs via Triangulations and CMSO
• Mixed Search Number of Permutation Graphs
• Two characterisations of the minimal triangulations of permutation graphs

This page was built for publication: Treewidth and Pathwidth of Permutation Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4863978)