Keyword : interval graph


A Linear-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Interval Graphs
Shin-ichi NAKAYAMA Shigeru MASUYAMA 
Publication:   
Publication Date: 2018/09/01
Vol. E101-D  No. 9 ; pp. 2235-2246
Type of Manuscript:  PAPER
Category: Fundamentals of Information Systems
Keyword: 
spanning treeinterval graphalgorithm
 Summary | Full Text:PDF(1.2MB)

Reconfiguration of Steiner Trees in an Unweighted Graph
Haruka MIZUTA Takehiro ITO Xiao ZHOU 
Publication:   
Publication Date: 2017/07/01
Vol. E100-A  No. 7 ; pp. 1532-1540
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
cographcombinatorial reconfigurationinterval graphPSPACE-completesplit graphSteiner tree
 Summary | Full Text:PDF(662.8KB)

A Tight Analysis of Kierstead-Trotter Algorithm for Online Unit Interval Coloring
Tetsuya ARAKI Koji M. KOBAYASHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2016/10/01
Vol. E99-A  No. 10 ; pp. 1885-1887
Type of Manuscript:  LETTER
Category: Algorithms and Data Structures
Keyword: 
interval coloringunit intervalonline probleminterval graph
 Summary | Full Text:PDF(75.6KB)

Parallel Algorithms for Finding the Center of Interval and Circular-Arc Graphs
Fang Rong HSU Man Kwan SHAN 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/10/01
Vol. E86-A  No. 10 ; pp. 2704-2709
Type of Manuscript:  LETTER
Category: Graphs and Networks
Keyword: 
parallel algorithmsEREW PRAMcenter probleminterval graphcircular-arc graph
 Summary | Full Text:PDF(348.5KB)

An Algorithm for Solving the Minimum Vertex Ranking Spanning Tree Problem on Interval Graphs
Shin-ichi NAKAYAMA Shigeru MASUYAMA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/05/01
Vol. E86-A  No. 5 ; pp. 1019-1026
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
algorithmvertex rankingspanning treeinterval graph
 Summary | Full Text:PDF(301.5KB)

Algorithms for Generating Maximum Weight Independent Sets in Circle Graphs, Circular-Arc Overlap Graphs, and Spider Graphs
Masakuni TAKI Hirotaka HATAKENAKA Toshinobu KASHIWABARA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/08/25
Vol. E82-A  No. 8 ; pp. 1636-1640
Type of Manuscript:  PAPER
Category: Graphs and Networks
Keyword: 
circle graphindependent setgeneration algorithmintersection graphinterval graphoverlap graphspider graphcircular-arc overlap graph
 Summary | Full Text:PDF(421.1KB)

A Representation Diagram for Maximal Independent Sets of a Graph
Masakuni TAKI Sumio MASUDA Toshinobu KASHIWABARA 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1998/05/25
Vol. E81-A  No. 5 ; pp. 784-788
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
maximal independent setinterval graphcocomparability graphgeneration problem
 Summary | Full Text:PDF(498KB)