Premium
Network flow spanners
Author(s) -
Dragan Feodor F.,
Yan Chenyu
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20357
Subject(s) - computer science , steiner tree problem , flow network , theoretical computer science , mathematical optimization , mathematics
In this article, motivated by applications of ordinary (distance) spanners in communication networks and to address such issues as bandwidth constraints on network links, link failures, network survivability, etc., we introduce a new notion of flow spanner, where one seeks a spanning subgraph H = ( V , E ') of a graph G = ( V , E ) which provides a “good” approximation of the source‐sink flows in G . We formulate several variants of this problem and investigate their complexities. Special attention is given to the version where H is required to be a tree. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010