The Library
Computing the girth of a planar graph
Tools
UNSPECIFIED (2000) Computing the girth of a planar graph. In: 27th International Colloquium on Automata Languages and Programming (ICALP 2000), GENEVA, SWITZERLAND, JUL 09-15, 2000. Published in: AUTOMATA LANGUAGES AND PROGRAMMING, 1853 pp. 821-831. ISBN 3-540-67715-1. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
The girth of a graph G has been defined as the length of a shortest cycle of G. We design an O(n(5/4) log n) algorithm for finding the girth of an undirected n-vertex planar graph, giving the first o(n(2)) algorithm for this problem. Our approach combines several techniques such as graph separation, hammock decomposition, covering of a planar graph with graphs of small tree-width, and dynamic shortest path computation. We discuss extensions and generalizations of our result.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Series Name: | LECTURE NOTES IN COMPUTER SCIENCE | ||||
Journal or Publication Title: | AUTOMATA LANGUAGES AND PROGRAMMING | ||||
Publisher: | SPRINGER-VERLAG BERLIN | ||||
ISBN: | 3-540-67715-1 | ||||
ISSN: | 0302-9743 | ||||
Editor: | Montanari, U and Rolim, JDP and Welzl, E | ||||
Official Date: | 2000 | ||||
Dates: |
|
||||
Volume: | 1853 | ||||
Number of Pages: | 11 | ||||
Page Range: | pp. 821-831 | ||||
Publication Status: | Published | ||||
Title of Event: | 27th International Colloquium on Automata Languages and Programming (ICALP 2000) | ||||
Location of Event: | GENEVA, SWITZERLAND | ||||
Date(s) of Event: | JUL 09-15, 2000 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |