Graph Theoretic Investigations on Inefficiencies in Network Models
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2016
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910455385030656 |
|---|---|
| author | Cenciarelli, Pietro Gorla, Daniele Salvo, Ivano |
| author_facet | Cenciarelli, Pietro Gorla, Daniele Salvo, Ivano |
| contents | We consider network models where information items flow %are sent from a source to a sink node. We start with a model where routing is constrained by energy available on nodes in finite supply (like in Smartdust) and efficiency is related to energy consumption. We characterize graph topologies ensuring that every saturating flow under every energy-to-node assignment is maximum and provide a polynomial-time algorithm for checking this property. We then consider the standard flow networks with capacity on edges, where again efficiency is related to maximality of saturating flows, and a traffic model for selfish routing, where efficiency is related to latency at a Wardrop equilibrium. Finally, we show that all these forms of inefficiency yield different classes of graphs (apart from the acyclic case, where the last two forms generate the same class). Interestingly, in all cases inefficient graphs can be made efficient by removing edges; this resembles a well-known phenomenon, called Braess's paradox. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1603_01983 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | Graph Theoretic Investigations on Inefficiencies in Network Models Cenciarelli, Pietro Gorla, Daniele Salvo, Ivano Discrete Mathematics We consider network models where information items flow %are sent from a source to a sink node. We start with a model where routing is constrained by energy available on nodes in finite supply (like in Smartdust) and efficiency is related to energy consumption. We characterize graph topologies ensuring that every saturating flow under every energy-to-node assignment is maximum and provide a polynomial-time algorithm for checking this property. We then consider the standard flow networks with capacity on edges, where again efficiency is related to maximality of saturating flows, and a traffic model for selfish routing, where efficiency is related to latency at a Wardrop equilibrium. Finally, we show that all these forms of inefficiency yield different classes of graphs (apart from the acyclic case, where the last two forms generate the same class). Interestingly, in all cases inefficient graphs can be made efficient by removing edges; this resembles a well-known phenomenon, called Braess's paradox. |
| title | Graph Theoretic Investigations on Inefficiencies in Network Models |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/1603.01983 |