Computing Treewidth and Minimum Fill-In for Permutation Graphs in Linear Time.
Daniel MeisterPublished in: WG (2005)
Keyphrases
- bounded treewidth
- tree decompositions
- connected dominating set
- upper bound
- spanning tree
- directed graph
- worst case
- graph matching
- boolean functions
- graph theory
- dominating set
- graph theoretic
- space complexity
- simple polygon
- constraint graph
- graph representation
- minimum cost
- objective function
- graph structure
- decision problems
- search space
- data structure