A Polynomial Time Algorithm for Finding a Minimally Generalized Linear Interval Graph Pattern
スポンサーリンク
概要
- 論文の詳細を見る
A graph is an interval graph if and only if each vertex in the graph can be associated with an interval on the real line such that any two vertices are adjacent in the graph exactly when the corresponding intervals have a nonempty intersection. A number of interesting applications for interval graphs have been found in the literature. In order to find structural features common to structural data which can be represented by intervals, this paper proposes new interval graph structured patterns, called linear interval graph patterns, and a polynomial time algorithm for finding a minimally generalized linear interval graph pattern explaining a given finite set of interval graphs.
- 2009-02-01
著者
-
Yamasaki Hitoshi
Department Of Informatics Kyushu University
-
Shoudai Takayoshi
Department Of Informatics Kyushu University
-
Shoudai Takayoshi
Department Of Control Engineering And Science Kyushu Institute Of Technology
関連論文
- A Polynomial Time Algorithm for Finding a Minimally Generalized Linear Interval Graph Pattern
- Using Maximal Independent Sets to Solve Problems in Parallel
- Purity Dependence of the Anisortopy of Residual Electrical Resistivity in High-Purity Al Single Crystals
- Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data
- A P-Complete Language Describable with Iterated Shuffle