|Table of Contents|

Testing for the Consecutive One’s Property in Interval Graphs(PDF)

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

Issue:
2000年05期
Page:
433-436
Research Field:
Publishing date:

Info

Title:
Testing for the Consecutive One’s Property in Interval Graphs
Author(s):
QianJianping
School of Information,NUST,Nanjing 210094
Keywords:
very larg e scale integ rated circuit s mat rixs graphs ( mathemat ics) interval g raph
PACS:
-
DOI:
-
Abstract:
In desig n of VLSI, interval g raph is used in the grid matrix method. There is the consecutive one’s property in interval graphs. An algorithm is proposed to test the consecutive one’s property in interval graphs. It beg ins with AAT and determines the order of row s step by step, based on the relat ionship of inner product of row vectors. Consecut ive one’s property is determined in the end. The algorithm has more adaptable, practicable, convenient and ef fective compared w ith Fulkerson’ s algorithm.

References:

1 宋俊德, 辛德禄.超大规模集成电路与系统设计导论.北京: 电子科技大学出版社, 1989
2 Lekkerkerker C G, Boland J Ch. Representat ion of a finite g raph by a set of interv als on the r ealline. Fund Math, 1962, 51: 45~ 64
3 Fulkerso n D R, Gross O A. Incidence matrices and inter val g raphs. Pacific J Mat h, 1965, 15:835~ 855

Memo

Memo:
-
Last Update: 2013-03-25