Result: Wide diameters of de Bruijn graphs
Title:
Wide diameters of de Bruijn graphs
Authors:
Source:
Selected papers from the CTS Conference on Combinatorics and its Applications in Honor of Franck K. Hwang's 65th birthdayJournal of combinatorial optimization. 14(2-3):143-152
Publisher Information:
Norwell, MA: Springer, 2007.
Publication Year:
2007
Physical Description:
print, 1/4 p
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Flots dans les réseaux. Problèmes combinatoires, Flows in networks. Combinatorial problems, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Logiciel, Software, Systèmes informatiques et systèmes répartis. Interface utilisateur, Computer systems and distributed systems. User interface, Diamètre, Diameter, Diámetro, Graphe non orienté, Non directed graph, Grafo no orientado, Optimisation combinatoire, Combinatorial optimization, Optimización combinatoria, Réseau interconnexion, Interconnection network, Red interconexión, Réseau télécommunication, Telecommunication network, Red telecomunicación, Système réparti, Distributed system, Sistema repartido, Tolérance faute, Fault tolerance, Tolerancia falta, de Bruijn Internally disjoint path Wide diameter
Document Type:
Conference
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Applied Mathematics. NCTU, Hsinchu 300, Tawain, Province of China
ISSN:
1382-6905
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Operational research. Management
Operational research. Management
Accession Number:
edscal.19068013
Database:
PASCAL Archive
Further Information
The wide diameter of a graph is an important parameter to measure fault-tolerance of interconnection network. This paper proves that for any two vertices in de Bruijn undirected graph UB(d,n), there are 2d - 2 internally disjoint paths of length at most 2n + 1. Therefore, the (2d - 2)-wide diameter of UB(d, n) is not greater than 2n + 1.