A Polynomial Time Algorithm for Finding a Minimally Generalized Linear Interval Graph Pattern

• YAMASAKI Hitoshi

  Department of Informatics, Kyushu University

• SHOUDAI Takayoshi

  Department of Informatics, Kyushu University

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.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E92-D (2), 120-129, 2009

  The Institute of Electronics, Information and Communication Engineers

Keywords

• interval graphs
• PQ-trees
• graph structured patterns
• graph mining
• computational learning theory

Details

• CRID: 1390001204377749376
• NII Article ID: 10026807296
• NII Book ID: AA10826272
• DOI: 10.1587/transinf.e92.d.120
• ISSN: 17451361
• ISSN: 09168532
• Web Site: http://www.jstage.jst.go.jp/article/transinf/E92.D/2/E92.D_2_120/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed