Line digraph iterations and the (d,k) digraph problem

Home | About RECERCAT | Contact

Català | Castellano

All of RECERCAT

By Communities &
Collections By Defense Date By Authors By Titles By Subject

This Collection

By Defense Date By Authors By Titles By Subject

Statistics

View Statistics All RECERCAT

My RECERCAT

Other repositories directory

RECERCAT Home > Universitat Politècnica de Catalunya > Documents de recerca > View document

To access the full text documents, please follow this link: http://hdl.handle.net/2117/12657

dc.contributor	Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV
dc.contributor	Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
dc.contributor.author	Fiol Mora, Miquel Àngel
dc.contributor.author	Andrés Yebra, José Luis
dc.contributor.author	Alegre de Miguel, Ignacio
dc.date	1984-05
dc.identifier.citation	Fiol, M. A.; Andrés, J.; Alegre, I. Line digraph iterations and the (d,k) digraph problem. "IEEE transactions on computers", Maig 1984, vol. C-33, núm. 5, p. 400-403.
dc.identifier.citation	0018-9340
dc.identifier.uri	http://hdl.handle.net/2117/12657
dc.language.iso	eng
dc.rights	Attribution-NonCommercial-NoDerivs 3.0 Spain
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.subject	Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi matemàtica
dc.subject	Algorithms
dc.subject	Anàlisi matemàtica
dc.subject	Classificació AMS::68 Computer science::68W Algorithms
dc.title	Line digraph iterations and the (d,k) digraph problem
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/article
dc.description.abstract	This paper studies the behavior of the diameter and the average distance between vertices of the line digraph of a given digraph. The results obtained are then applied to the so-called (d, k) digraph problem, that is, to maximize the number of vertices in a digraph of maximum out-degree d and diameter k. By line digraph iterations it is possible to construct digraphs with a number of vertices larger than (d2 - l)/d2 times the (nonattainable) Moore bound. In particular, this solves the (d, k) digraph problem for k = 2. Also, the line digraph technique provides us with a simple local routing algorithm for the corresponding networks.

Show simple item record

All of RECERCAT

This Collection

Statistics

My RECERCAT

Related documents

Other documents of the same author