• DocumentCode
    2328443
  • Title

    Edge disjoint graph spanners of complete graphs and complete digraphs

  • Author

    Laforest, Christian ; Liestman, Arthur L. ; Shermer, Thomas C. ; Sotteau, Dominique

  • Author_Institution
    Lab. de Recherche en Inf., Univ. de Paris-Sud, Orsay, France
  • Volume
    1
  • fYear
    1997
  • fDate
    7-10 Jan 1997
  • Firstpage
    191
  • Abstract
    A spanning subgraph S=(V, E´) of a connected simple graph (digraph)G=(V, E) is a f(x)-spanner if for any pair of nodes u and v, d S(u, v)⩽f(dG(u, v)) where dG and d S are the usual distance functions in graphs (digraphs) G and S, respectively. The delay of the f(x)-spanner is f(x)-x. The authors investigate the existence of multiple edge-disjoint spanners in complete graphs and complete digraphs
  • Keywords
    graph theory; multiprocessor interconnection networks; complete digraphs; complete graphs; connected simple graph; delay; distance functions; edge disjoint graph spanners; interconnection networks; multiple edge-disjoint spanners; spanning subgraph; Art; Computer networks; Concurrent computing; Costs; Delay; Multiprocessor interconnection networks; Network topology; Parallel machines; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    System Sciences, 1997, Proceedings of the Thirtieth Hawaii International Conference on
  • Conference_Location
    Wailea, HI
  • ISSN
    1060-3425
  • Print_ISBN
    0-8186-7743-0
  • Type

    conf

  • DOI
    10.1109/HICSS.1997.667214
  • Filename
    667214
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2328443