Treewidth and Minimum Fill-in on d-Trapezoid Graphs
From MaRDI portal
Publication:4215725
DOI10.7155/jgaa.00008zbMath0905.68101OpenAlexW3022074675MaRDI QIDQ4215725
Haiko Müller, Ton Kloks, Dieter Kratsch, Hans L. Bodlaender
Publication date: 28 October 1998
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/48061
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items (26)
Minimal triangulations of graphs: a survey ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Edge Search Number of Cographs in Linear Time ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Efficient algorithm for the vertex connectivity of trapezoid graphs ⋮ Approximating Pathwidth for Graphs of Small Treewidth ⋮ Characterizing and Computing Minimal Cograph Completions ⋮ Mixed Search Number of Permutation Graphs ⋮ Edge search number of cographs ⋮ Restricted vertex multicut on permutation graphs ⋮ A revisit of the scheme for computing treewidth and minimum fill-in ⋮ 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 ⋮ Approximation of RNA multiple structural alignment ⋮ A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs ⋮ Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ Computing the branchwidth of interval graphs ⋮ Characterizing and computing minimal cograph completions ⋮ On the interval completion of chordal graphs ⋮ Treewidth and minimum fill-in on permutation graphs in linear time ⋮ Happy set problem on subclasses of co-comparability graphs ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ Algorithms and complexity of \(s\)-club cluster vertex deletion
This page was built for publication: Treewidth and Minimum Fill-in on d-Trapezoid Graphs