Volume

Dagstuhl Seminar Proceedings, Volume 5361

Publication Details

  • published at: 2006-05-08
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.05361.1
05361 Abstracts Collection – Algorithmic Aspects of Large and Complex Networks

Authors: Stefano Leonardi, Friedhelm Meyer auf der Heide, and Dorothea Wagner

Abstract
From 04.09.05 to 09.09.05, the Dagstuhl Seminar 05361 ``Algorithmic Aspects of Large and Complex Networks'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Stefano Leonardi, Friedhelm Meyer auf der Heide, and Dorothea Wagner. 05361 Abstracts Collection – Algorithmic Aspects of Large and Complex Networks. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{leonardi_et_al:DagSemProc.05361.1,
  author =	{Leonardi, Stefano and Meyer auf der Heide, Friedhelm and Wagner, Dorothea},
  title =	{{05361 Abstracts Collection – Algorithmic Aspects of Large and Complex Networks}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.1},
  URN =		{urn:nbn:de:0030-drops-5702},
  doi =		{10.4230/DagSemProc.05361.1},
  annote =	{Keywords: Algorithms, Large and Complex Networks}
}
Document
DOI: 10.4230/DagSemProc.05361.2
A Cost Mechanism for Fair Pricing of Resource Usage

Authors: Marios Mavronicolas, Panagiota Panagopoulou, and Paul G. Spirakis

Abstract
We propose a simple and intuitive cost mechanism which assigns costs for the competitive usage of $m$ resources by $n$ selfish agents. Each agent has an individual demand; demands are drawn according to some probability distribution. The cost paid by an agent for a resource she chooses is the total demand put on the resource divided by the number of agents who chose that same resource. So, resources charge costs in an equitable, fair way, while each resource makes no profit out of the agents. We call our model the Fair Pricing model. Its fair cost mechanism induces a non-cooperative game among the agents. To evaluate the Nash equilibria of this game, we introduce the Diffuse Price of Anarchy, as an extension of the Price of Anarchy that takes into account the probability distribution on the demands. We prove: (1) Pure Nash equilibria may not exist, unless all chosen demands are identical; in contrast, a fully mixed Nash equilibrium exists for all possible choices of the demands. Further on, the fully mixed Nash equilibrium is the unique Nash equilibrium in case there are only two agents. (2) In the worst-case choice of demands, the Price of Anarchy is $Theta (n)$; for the special case of two agents, the Price of Anarchy is less than $2 - frac{1}{m}$. (3) Assume now that demands are drawn from a bounded, independent probability distribution, where all demands are identically distributed and each is at most a (universal for the class) constant times its expectation. Then, the Diffuse Price of Anarchy is at most that same constant, which is just $2$ when each demand is distributed symmetrically around its expectation.
Cite as

Marios Mavronicolas, Panagiota Panagopoulou, and Paul G. Spirakis. A Cost Mechanism for Fair Pricing of Resource Usage. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{mavronicolas_et_al:DagSemProc.05361.2,
  author =	{Mavronicolas, Marios and Panagopoulou, Panagiota and Spirakis, Paul G.},
  title =	{{A Cost Mechanism for Fair Pricing of Resource Usage}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.2},
  URN =		{urn:nbn:de:0030-drops-5646},
  doi =		{10.4230/DagSemProc.05361.2},
  annote =	{Keywords: Cost Sharing, Diffuse Price of Anarchy, Fair Pricing, Resources}
}
Document
DOI: 10.4230/DagSemProc.05361.3
A Hybrid Model for Drawing Dynamic and Evolving Graphs

Authors: Marco Gaertler and Dorothea Wagner

Abstract
Dynamic processes frequently occur in many applications. Visualizations of dynamically evolving data, for example as part of the data analysis, are typically restricted to a cumulative static view or an animation/sequential view. Both methods have their benefits and are often complementary in their use. We present a hybrid model that combines the two techniques. This is accomplished by 2.5D drawings which are calculated in an incremental way. The method has been evaluated on collaboration networks.
Cite as

Marco Gaertler and Dorothea Wagner. A Hybrid Model for Drawing Dynamic and Evolving Graphs. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{gaertler_et_al:DagSemProc.05361.3,
  author =	{Gaertler, Marco and Wagner, Dorothea},
  title =	{{A Hybrid Model for Drawing Dynamic and Evolving Graphs}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.3},
  URN =		{urn:nbn:de:0030-drops-5683},
  doi =		{10.4230/DagSemProc.05361.3},
  annote =	{Keywords: Visualization dynamic/evolving graphs 2.5D}
}
Document
DOI: 10.4230/DagSemProc.05361.4
Computing earliest arrival flows with multiple sources

Authors: Nadine Baumann and Martin Skutella

Abstract
Earliest arrival flows are motivated by applications related to evacuation. Given a network with capacities and transit times on the arcs, a subset of source nodes with supplies and a sink node, the task is to send the given supplies from the sources to the sink "as quickly as possible". The latter requirement is made more precise by the earliest arrival property which requires that the total amount of flow that has arrived at the sink is maximal for all points in time simultaneously. It is a classical result from the 1970s that, for the special case of a single source node, earliest arrival flows do exist and can be computed by essentially applying the Successive Shortest Path Algorithm for min-cost flow computations. While it has previously been observed that an earliest arrival flow still exists for multiple sources, the problem of computing one efficiently has been open. We present an exact algorithm for this problem whose running time is strongly polynomial in the input plus output size of the problem.
Cite as

Nadine Baumann and Martin Skutella. Computing earliest arrival flows with multiple sources. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{baumann_et_al:DagSemProc.05361.4,
  author =	{Baumann, Nadine and Skutella, Martin},
  title =	{{Computing earliest arrival flows with multiple sources}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.4},
  URN =		{urn:nbn:de:0030-drops-5672},
  doi =		{10.4230/DagSemProc.05361.4},
  annote =	{Keywords: Networks, flows over time, dynamic flows, earliest arrival, evacuation}
}
Document
DOI: 10.4230/DagSemProc.05361.5
Cost Sharing Mechanisms for Fair Pricing of Resources Usage

Authors: Marios Mavronicolas, Panagiota Panagopoulou, and Paul G. Spirakis

Abstract
We propose a simple and intuitive cost mechanism which assigns costs for the competitive usage of $m$ resources by $n$ selfish agents. Each agent has an individual demand; demands are drawn according to some probability distribution. The cost paid by an agent for a resource she chooses is the total demand put on the resource divided by the number of agents who chose that same resource. So, resources charge costs in an equitable, fair way, while each resource makes no profit out of the agents. We call our model the Fair Pricing model. Its fair cost mechanism induces a non-cooperative game among the agents. To evaluate the Nash equilibria of this game, we introduce the Diffuse Price of Anarchy, as an extension of the Price of Anarchy that takes into account the probability distribution on the demands. We prove: (1) Pure Nash equilibria may not exist, unless all chosen demands are identical. In contrast, we have been able to prove that pure Nash equilibria do exist for two closely related cost sharing models, namely the Average Cost Pricing and the Serial Cost Sharing models. (2) A fully mixed Nash equilibrium exists for all possible choices of the demands. Further on, the fully mixed Nash equilibrium is the unique Nash equilibrium in case there are only two agents. (3) In the worst-case choice of demands, the Price of Anarchy is $Theta (n)$; for the special case of two agents, the Price of Anarchy is less than $2 - frac{1}{m}$. (4) Assume now that demands are drawn from a bounded, independent probability distribution, where all demands are identically distributed and each is at most a (universal for the class) constant times its expectation. Then, the Diffuse Price of Anarchy is at most that same constant, which is just 2 when each demand is distributed symmetrically around its expectation.
Cite as

Marios Mavronicolas, Panagiota Panagopoulou, and Paul G. Spirakis. Cost Sharing Mechanisms for Fair Pricing of Resources Usage. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{mavronicolas_et_al:DagSemProc.05361.5,
  author =	{Mavronicolas, Marios and Panagopoulou, Panagiota and Spirakis, Paul G.},
  title =	{{Cost Sharing Mechanisms for Fair Pricing of Resources Usage}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.5},
  URN =		{urn:nbn:de:0030-drops-5665},
  doi =		{10.4230/DagSemProc.05361.5},
  annote =	{Keywords: Cost Sharing, Diffuse Price of Anarchy, Fair Pricing, Resources}
}
Document
DOI: 10.4230/DagSemProc.05361.6
Deterministic boundary recongnition and topology extraction for large sensor networks

Authors: Sándor Fekete, Alexander Kröller, Dennis Pfisterer, and Stefan Fischer

Abstract
We present a new framework for the crucial challenge of self-organization of a large sensor network. The basic scenario can be described as follows: Given a large swarm of immobile sensor nodes that have been scattered in a polygonal region, such as a street network. Nodes have no knowledge of size or shape of the environment or the position of other nodes. Moreover, they have no way of measuring coordinates, geometric distances to other nodes, or their direction. Their only way of interacting with other nodes is to send or to receive messages from any node that is within communication range. The objective is to develop algorithms and protocols that allow self-organization of the swarm into large-scale structures that reflect the structure of the street network, setting the stage for global routing, tracking and guiding algorithms. Our algorithms work in two stages: boundary recognition and topology extraction. All steps are strictly deterministic, yield fast distributed algorithms, and make no assumption on the distribution of nodes in the environment, other than sufficient density.
Cite as

Sándor Fekete, Alexander Kröller, Dennis Pfisterer, and Stefan Fischer. Deterministic boundary recongnition and topology extraction for large sensor networks. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.05361.6,
  author =	{Fekete, S\'{a}ndor and Kr\"{o}ller, Alexander and Pfisterer, Dennis and Fischer, Stefan},
  title =	{{Deterministic boundary recongnition and topology extraction for large sensor networks}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.6},
  URN =		{urn:nbn:de:0030-drops-5632},
  doi =		{10.4230/DagSemProc.05361.6},
  annote =	{Keywords: Distributed algorithms, sensor networks, boundary recognition, topology extraction}
}
Document
DOI: 10.4230/DagSemProc.05361.7
Force-Directed Approaches to Sensor Network Localization

Authors: Stephen G. Kobourov, Alon Efrat, David Forrester, and Anand Iyer

Abstract
In many sensor network applications it is necessary to compute low-error localization of the sensor nodes. Although embedding a GPS unit on each node would solve the problem for many outdoor applications, the cost of this solution for large networks is prohibitively high. We consider static and mobile network localization approaches that make use of the local neighborhood information, in the form of relative distances and angles to nearby nodes, gathered through simpler and less costly devices (RF, ultrasound based range sensors, or antenna arrays). Our algorithms do not make any assumptions about the existence of anchor nodes capable of locating themselves, nor about the knowledge of an initial localization to start with. Instead, we rely on a multi-scale force-directed approach, utilizing range and angle data through dead reckoning. We show that our localization algorithms are robust and scale well with network size.
Cite as

Stephen G. Kobourov, Alon Efrat, David Forrester, and Anand Iyer. Force-Directed Approaches to Sensor Network Localization. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{kobourov_et_al:DagSemProc.05361.7,
  author =	{Kobourov, Stephen G. and Efrat, Alon and Forrester, David and Iyer, Anand},
  title =	{{Force-Directed Approaches to Sensor Network Localization}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.7},
  URN =		{urn:nbn:de:0030-drops-5693},
  doi =		{10.4230/DagSemProc.05361.7},
  annote =	{Keywords: Sensor network localization, multi-scale force-directed approach, dead reckoning}
}
Document
DOI: 10.4230/DagSemProc.05361.8
Friends for Free: Self-Organizing Artificial Social Networks for Trust and Cooperation

Authors: David Hales and Stefano Arteconi

Abstract
By harvesting friendship networks from e-mail contacts or instant message "buddy lists" Peer-to-Peer (P2P) applications can improve performance in low trust environments such as the Internet. However, natural social networks are not always suitable, reliable or available. We propose an algorithm (SLACER) that allows peer nodes to create and manage their own friendship networks. We evaluate performance using a canonical test application, requiring cooperation between peers for socially optimal outcomes. The Artificial Social Networks (ASN) produced are connected, cooperative and robust - possessing many of the disable properties of human friendship networks such as trust between friends (directly linked peers) and short paths linking everyone via a chain of friends. In addition to new application possibilities, SLACER could supply ASN to P2P applications that currently depend on human social networks thus transforming them into fully autonomous, self-managing systems.
Cite as

David Hales and Stefano Arteconi. Friends for Free: Self-Organizing Artificial Social Networks for Trust and Cooperation. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{hales_et_al:DagSemProc.05361.8,
  author =	{Hales, David and Arteconi, Stefano},
  title =	{{Friends for Free: Self-Organizing Artificial Social Networks for Trust and Cooperation}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.8},
  URN =		{urn:nbn:de:0030-drops-5659},
  doi =		{10.4230/DagSemProc.05361.8},
  annote =	{Keywords: Evolution of cooperation, Evolving Networks, P2P, Prisoner's Dilemma, Tags}
}

Filters

  • Authors
  • A
  • Arteconi, Stefano
  • B
  • Baumann, Nadine
  • E
  • Efrat, Alon
  • F
  • Fekete, Sándor
  • Fischer, Stefan
  • Forrester, David
  • G
  • Gaertler, Marco
  • H
  • Hales, David
  • I
  • Iyer, Anand
  • K
  • Kobourov, Stephen G.
  • Kröller, Alexander
  • L
  • Leonardi, Stefano
  • M
  • Mavronicolas, Marios
  • Meyer auf der Heide, Friedhelm
  • P
  • Panagopoulou, Panagiota
  • Pfisterer, Dennis
  • S
  • Skutella, Martin
  • Spirakis, Paul G.
  • W
  • Wagner, Dorothea

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact