PQR-trees and undirected path graphs.
详细信息
文摘
In [1] Booth and Lueker introduce PQ-trees and an algorithm solving the following problem. Given a set U and a family of subsets {S 0, ..., Sz-1} of U, output a data structure (PQ-tree) capturing all embeddings of U onto a path such that each Si is a subpath of that path. Their algorithm provides a linear time recognition algorithm for interval graphs (intersection graphs of subpaths of a path) which outputs a PQ-tree capturing all subpaths of a path intersection representations of an interval graph.;We introduce PQR-trees, generalizing PQ-trees [1], and an algorithm solving a similar problem where U is embedded in a tree and a PQR-tree is produced. Our algorithm provides a new recognition algorithm for path graphs (intersection graphs of paths in a tree) which outputs a PQR-tree capturing all paths in a tree intersection representations of a path graph.