Titlebook: Structural Information and Communication Complexity; 15th International C Alexander A. Shvartsman,Pascal Felber Conference proceedings 2008

CERE

Equal-Area Locus-Based Convex Polygon Decomposition points positioned arbitrarily inside ., the task is to divide . into . equal area convex parts, each containing exactly one point of .. The problem is motivated by a terrain covering task for a swarm of autonomous mobile robots. The algorithm runs in time .(.. + ..log.).

开始发作

On the Power of Local Orientationsach vertex have locally-unique labels – port names..We define a pre-processing phase that enables a right-hand rule using agent (RH-agent) to traverse the entire graph. For this phase we design an algorithm for an agent that performs the precomputation. The agent will alter the network by modifying

妨碍

Best Effort and Priority Queuing Policies for Buffered Crossbar Switchess, a small buffer is associated with each crosspoint. Due to the introduction of crossbar buffers, output and input contention is eliminated, and the scheduling process is greatly simplified. We analyze the performance of switch policies by means of competitive analysis, where a uniform guarantee is

Resection

Word of Mouth: Rumor Dissemination in Social Networksr propagation, seeking to maximize the number of persuaded nodes. We use concepts of game theory and location theory and model the selection of starting nodes for the rumors as a strategic game. We show that computing the optimal strategy for both the first and the second player is NP-complete, even

Mnemonics

尽管

Computing Approximate Nash Equilibria in Network Congestion Gamesy .> 0, but the reductions are based on artificial and steep delay functions with the property that already two players using the same resource cause a delay that is significantly larger than the delay for a single player..We consider network congestion games with delay functions such as polynomials

Collar

On the Performance of Beauquier and Debas’ Self-stabilizing Algorithm for Mutual Exclusionion on a ring of processors. In [BD95] a similar three state algorithm with an upper bound of . and a lower bound of . were presented for its stabilization time. For this later algorithm we prove an upper bound of ., and show a lower bound of .. − .(.).

Medicare

Gathering Problem of Two Asynchronous Mobile Robots with Semi-dynamic Compassesmproves the limit of difference to ./3. This is shown with the fully asynchronous robot model CORDA. Configurations and executions of robot systems for CORDA with dynamic compasses are formalised. In order to deal with behaviors of robots a concept of relative configurations is also introduced.

雪白

Computing Frequent Elements Using Gossipprove that the algorithm converges to the approximate frequent elements with high probability, and provide bounds on the time till convergence. To our knowledge, this is the first work on computing frequent elements using gossip.

脊椎动物