JAIST Repository >
Research Center for Advanced Computing Infrastructure >
Articles >
Journal Articles >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10119/3277

Title: Laminar structure of ptolemaic graphs and its applications
Authors: Uehara, R
Uno, Y
Keywords: algorithmic graph theory
data structure
Hamiltonian cycle
intersection model
ptolemaic graphs
Issue Date: 2005
Publisher: SPRINGER-VERLAG
Magazine name: Lecture Notes in Computer Science : including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics
Volume: 3827
Start page: 186
End page: 195
DOI: 10.1007/11602613_20
Abstract: 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, and it is 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, which 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.
Rights: This is the author-created version of Springer Berlin / Heidelberg, Ryuhei Uehara and Yushi Uno, Lecture Notes in Computer Science(Algorithms and Computation), 3827, 2005, 186-195. The original publication is available at www.springerlink.com, http://www.springerlink.com/content/pk7x44w4t8331085
URI: http://hdl.handle.net/10119/3277
Material Type: author
Appears in Collections:f10-1. 雑誌掲載論文 (Journal Articles)

Files in This Item:

File Description SizeFormat
S-50.pdf157KbAdobe PDFView/Open

All items in DSpace are protected by copyright, with all rights reserved.

 


Contact : Library Information Section, JAIST (ir-sys[at]ml.jaist.ac.jp)