Treewidth: Computations and Approximations
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Testing superperfection of k-trees and triangulating 3-colored graphs results in approximating treewidth and pathwidth for some classes of perfect graphs.
Abstract
and basic terminology.- Preliminaries.- Testing superperfection of k-trees.- Triangulating 3-colored graphs.- Only few graphs have bounded treewidth.- Approximating treewidth and pathwidth of a graph.- Approximating treewidth and pathwidth for some classes of perfect graphs.- Treewidth of chordal bipartite graphs.- Treewidth and pathwidth of permutation graphs.- Treewidth of circle graphs.- Finding all minimal separators of a graph.- Treewidth and pathwidth of cocomparability graphs of bounded dimension.- Pathwidth of pathwidth-bounded graphs.- Treewidth of treewidth-bounded graphs.- Recognizing treewidth-bounded graphs.