IEICE TRANSACTIONS on Information
A Polynomial Time Algorithm for Finding a Minimally Generalized Linear Interval Graph Pattern
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E92-D No.2 pp.120-129
- Publication Date
- 2009/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E92.D.120
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hitoshi YAMASAKI, Takayoshi SHOUDAI, "A Polynomial Time Algorithm for Finding a Minimally Generalized Linear Interval Graph Pattern" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 2, pp. 120-129, February 2009, doi: 10.1587/transinf.E92.D.120.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.120/_p
Copy
@ARTICLE{e92-d_2_120,
author={Hitoshi YAMASAKI, Takayoshi SHOUDAI, },
journal={IEICE TRANSACTIONS on Information},
title={A Polynomial Time Algorithm for Finding a Minimally Generalized Linear Interval Graph Pattern},
year={2009},
volume={E92-D},
number={2},
pages={120-129},
abstract={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.},
keywords={},
doi={10.1587/transinf.E92.D.120},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - A Polynomial Time Algorithm for Finding a Minimally Generalized Linear Interval Graph Pattern
T2 - IEICE TRANSACTIONS on Information
SP - 120
EP - 129
AU - Hitoshi YAMASAKI
AU - Takayoshi SHOUDAI
PY - 2009
DO - 10.1587/transinf.E92.D.120
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2009
AB - 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.
ER -
English
