Treewidth and Pathwidth of Permutation Graphs

DOI10.1137/S089548019223992XzbMATH Open0840.05087DBLPjournals/siamdm/BodlaenderKK95OpenAlexW2091208300WikidataQ56560643 ScholiaQ56560643MaRDI QIDQ4863978FDOQ4863978

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)

Cited In (52)

The firebreak problem
A linear time algorithm to list the minimal separators of chordal graphs
Locally definable vertex set properties are efficiently enumerable
How to use the minimal separators of a graph for its chordal triangulation
A Characterisation of the Minimal Triangulations of Permutation Graphs
On the vertex ranking problem for trapezoid, circular-arc and other graphs
Computing \(K\)-terminal reliability of \(d\)-trapezoid graphs
Treewidth and minimum fill-in on permutation graphs in linear time
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
Constructive linear time algorithms for branchwidth
Edge Search Number of Cographs in Linear Time
On probe permutation graphs
Approximating the treewidth of AT-free graphs.
Edge search number of cographs
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
GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
Computing directed pathwidth in \(O(1.89^n)\) time
Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
Chordal embeddings of planar graphs
Approximate search strategies for weighted trees
Computing branchwidth via efficient triangulations and blocks
Restricted vertex multicut on permutation graphs
On finding separators in temporal split and permutation graphs
On finding separators in temporal split and permutation graphs
Linear rank-width and linear clique-width of trees
Edge and node searching problems on trees
Treewidth of cocomparability graphs and a new order-theoretic parameter
Measuring the vulnerability for classes of intersection graphs
Finding a maximum minimal separator: graph classes and fixed-parameter tractability
The firefighter problem on graph classes
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
On the Maximum Weight Minimal Separator
Node-searching problem on block graphs
Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators
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
Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
As Time Goes By: Reflections on Treewidth for Temporal Graphs
Large Induced Subgraphs via Triangulations and CMSO
Mixed Search Number of Permutation Graphs
Pathwidth is NP-Hard for Weighted Trees
Two characterisations of the minimal triangulations of permutation graphs

Recommendations

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)