Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
ON FAULT-TOLERANT EMBEDDING OF HAMILTONIAN CIRCUITS IN-LINE DIGRAPH INTERCONNECTION NETWORKS
Autore:
VISWANATHAN S; CZABARKA E; SENGUPTA A;
Indirizzi:
UNIV S CAROLINA,DEPT COMP SCI COLUMBIA SC 29208 UNIV S CAROLINA,DEPT COMP SCI COLUMBIA SC 29208 UNIV S CAROLINA,DEPT MATH COLUMBIA SC 29208
Titolo Testata:
Information processing letters
fascicolo: 5, volume: 57, anno: 1996,
pagine: 265 - 271
SICI:
0020-0190(1996)57:5<265:OFEOHC>2.0.ZU;2-G
Fonte:
ISI
Lingua:
ENG
Soggetto:
GRAPHS; TOURS;
Keywords:
EMBEDDING; FAULT TOLERANCE; HAMILTONIAN CIRCUIT; DEBRUIJN AND KAUTZ DIGRAPHS;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
CompuMath Citation Index
Science Citation Index Expanded
Citazioni:
9
Recensione:
Indirizzi per estratti:
Citazione:
S. Viswanathan et al., "ON FAULT-TOLERANT EMBEDDING OF HAMILTONIAN CIRCUITS IN-LINE DIGRAPH INTERCONNECTION NETWORKS", Information processing letters, 57(5), 1996, pp. 265-271

Abstract

Interconnection networks based on directed line graphs have a nice property: an Euler tour in the digraph G translates to a Hamiltonian circuit in the line digraph L(G). Moreover, the existence of a Hamiltonian circuit in L(G) implies that G must be Eulerian, While Hamiltonian circuits are hard to find in the presence of link failures, the equivalent Euler tours are relatively easy to find in the presence of forbidden link pairs (corresponding to the link failures in L(G)). We explorethis idea and present necessary and sufficient conditions for the existence of fault-free Euler tour in a digraph. We also present an algorithm to find such an Euler tour when it exists.

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