Treewidth and Minimum Fill-in on d-Trapezoid Graphs

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

Mathematics Subject Classification ID

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