Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Diameter determination on restricted graph families
Autore:
Corneil, DG; Dragan, FF; Habib, M; Paul, C;
Indirizzi:
Univ Toronto, Dept Comp Sci, Toronto, ON M5S 3G4, Canada Univ Toronto Toronto ON Canada M5S 3G4 p Sci, Toronto, ON M5S 3G4, Canada Univ Calif Los Angeles, Dept Comp Sci, Los Angeles, CA 90095 USA Univ Calif Los Angeles Los Angeles CA USA 90095 Los Angeles, CA 90095 USA Univ Montpellier 2, CNRS, LIRMM, UMR, F-34392 Montpellier, France Univ Montpellier 2 Montpellier France F-34392 -34392 Montpellier, France
Titolo Testata:
DISCRETE APPLIED MATHEMATICS
fascicolo: 2-3, volume: 113, anno: 2001,
pagine: 143 - 166
Fonte:
ISI
Lingua:
ENG
Soggetto:
LINEAR-TIME ALGORITHMS; TRIPLE-FREE GRAPHS; LEXBFS-ORDERINGS; PATHS; PAIRS;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
30
Recensione:
Indirizzi per estratti:
Indirizzo: Corneil, DG Univ Toronto, Dept Comp Sci, Toronto, ON M5S 3G4, Canada Univ Toronto Toronto ON Canada M5S 3G4 to, ON M5S 3G4, Canada
Citazione:
D.G. Corneil et al., "Diameter determination on restricted graph families", DISCR APP M, 113(2-3), 2001, pp. 143-166

Abstract

Determining the diameter of a graph is a fundamental graph operation. yet no efficient (i.e. linear or quadratic time) algorithm is known. In this paper, we examine the diameter problem on chordal graphs and AT-free graphs and show that a very simple (linear time) 2-sweep LexBFS algorithm identifies a vertex of maximum eccentricity unless the given graph has a specified induced subgraph (it was previously known that a single LexBFS algorithm is guaranteed to end at a vertex that is within 1 of the diameter for chordal graphs and AT-free graphs). As a consequence of the forbidden induced subgraph result on chordal graphs, our algorithm is guaranteed to work optimallyfor directed path graphs (it was previously known that a single LexBFS algorithm is guaranteed to work optimally for interval graphs). (C) 2001 Elsevier Science B.V. All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 31/03/20 alle ore 05:08:31