Research work · 2004
Canonical Data Structure for Probe Interval Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science)
Ryuhei Uehara
Institutional Repositories DataBase (IRDB)
Abstract
Probe interval graphs are introduced to deal $\mathrm{w}$ as ageneralization of interval graphs.Polynomial 1 known.However, the complexity of the graph $\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{m}|$ this paper, extended $\lambda 4\mathcal{P}Q$ -trees are proposed to 1 $\lambda 4\mathcal{P}Q$ -tree for given probe interval graph can be $\mathrm{C}\mathrm{O}\Gamma_{l}^{1}$ tree is canonical, and hence we can solve the graph $\mathrm{i}$ time.Using the tree, we can determine that any two relation cannot be determined without an $\mathrm{e}\mathrm{x}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{m}|$ nonprobe that would be probed in the next $\mathrm{e}\mathrm{x}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{m}\epsilon$ interval graphs for given probe interval graph.