Paper Abstract and Keywords |
Presentation |
2005-09-15 10:50
Laminar Structure of Ptolemaic Graphs and Its Applications Ryuhei Uehara (JAIST), Yushi Uno (Osaka Pref. Univ.) |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
Ptolemaic graphs are graphs that satisfy the Ptolemaic inequality for any four vertices.
The graph class coincides with the intersection of chordal graphs and distance hereditary graphs.
The graph class can also be seen as a natural generalization of block graphs (and hence trees).
In this paper, a new characterization of ptolemaic graphs is presented.
It is a laminar structure of cliques, and leads us to a canonical tree representation.
The tree representation gives a simple intersection model for ptolemaic graphs.
The tree representation is constructed in linear time from
a perfect elimination ordering obtained by the lexicographic breadth first search.
Hence the recognition and the graph isomorphism for ptolemaic graphs can be solved in linear time.
Using the tree representation,
we also give an O(n) time algorithm for the Hamiltonian cycle problem. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
Algorithmic graph theory / data structure / Hamiltonian cycle / intersection model / ptolemaic graph / / / |
Reference Info. |
IEICE Tech. Rep., vol. 105, no. 273, COMP2005-30, pp. 17-24, Sept. 2005. |
Paper # |
COMP2005-30 |
Date of Issue |
2005-09-08 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
Download PDF |
|
Conference Information |
Committee |
COMP |
Conference Date |
2005-09-15 - 2005-09-15 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Osaka Univ., Toyonaka Campus |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
COMP |
Conference Code |
2005-09-COMP |
Language |
English |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Laminar Structure of Ptolemaic Graphs and Its Applications |
Sub Title (in English) |
|
Keyword(1) |
Algorithmic graph theory |
Keyword(2) |
data structure |
Keyword(3) |
Hamiltonian cycle |
Keyword(4) |
intersection model |
Keyword(5) |
ptolemaic graph |
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Ryuhei Uehara |
1st Author's Affiliation |
Japan Advanced Institute of Science and Technology (JAIST) |
2nd Author's Name |
Yushi Uno |
2nd Author's Affiliation |
Osaka Prefecture University (Osaka Pref. Univ.) |
3rd Author's Name |
|
3rd Author's Affiliation |
() |
4th Author's Name |
|
4th Author's Affiliation |
() |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2005-09-15 10:50:00 |
Presentation Time |
35 minutes |
Registration for |
COMP |
Paper # |
COMP2005-30 |
Volume (vol) |
vol.105 |
Number (no) |
no.273 |
Page |
pp.17-24 |
#Pages |
8 |
Date of Issue |
2005-09-08 (COMP) |