Premium
Note: Small integral flows need only sparse networks
Author(s) -
Althöfer Ingo
Publication year - 1994
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.3230240409
Subject(s) - spanner , combinatorics , flow (mathematics) , sequence (biology) , mathematics , enhanced data rates for gsm evolution , value (mathematics) , flow network , discrete mathematics , computer science , geometry , telecommunications , statistics , distributed computing , biology , genetics
Consider a network on n + 1 vertices and two s ‐ t ‐flows f and f * of equal value. f * is called a flow spanner of f if f *( e ) ⩽ f ( e ) for every edge e . In this note, we prove that every integral flow f of value n 2 ‐ε (0 ⩽ ε ⩽ 2) has a flow spanner f * that uses at most O ( n 2 ‐ε/2) many edges. A sequence of examples shows that this result is asymptotically optimal. © 1994 by John Wiley & Sons, Inc.