Note: Small integral flows need only sparse networks | Zendy

Althöfer Ingo | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research