Titlebook: Structural Information and Communication Complexity; 11th International C Ratislav Královic̆,Ondrej Sýkora Conference proceedings 2004 Spri

Melanoma

On Approximability of the Independent Set Problem for Low Degree Graphs, .≥ 3. The degree-three case plays a role of the central problem, as many of the results for the other problems use reductions to it. Our careful analysis of approximation algorithms of Berman and Fujito for 3-. shows that one can achieve approximation ratio arbitrarily close to .. Improvements of a

Accord

Asynchronous Broadcast in Radio Networks,d by the source node. The timing of arrivals of messages is controlled by adversaries. We consider three different adversaries. The edge adversary can have a transmitted message delivered at different times to different recipients. The crash adversary is the edge one augmented by the ability to cras

使成波状

Two-Hop Virtual Path Layout in Tori,pattern, the problem consists of designing a virtual network with a given diameter ., which can be embedded in the physical one with a minimum congestion (the congestion is the maximum load of a physical link). Here we propose a method to solve this problem when the diameter is 2. We use this method

宽大

Robot Convergence via Center-of-Gravity Algorithms,ors. A natural algorithm for the problem is based on requiring each robot to move towards the robots’ center of gravity. The paper proves the correctness of the center-of-gravity algorithm in the semi-synchronous model for any number of robots, and its correctness in the fully asynchronous model for

啜泣

表两个

Picks-Disease

Sparse Additive Spanners for Bounded Tree-Length Graphs,t most ., i.e., the tree-length . graphs. For such graphs we construct additive 2.-spanners with .(.log .) edges, and additive 4.-spanners with .(.) edges. This provides new upper bounds for chordal graphs for which .=1. We also show a lower bound, and prove that there are graphs of tree-length . fo

净礼

Bravado

鲁莽

Mobile Agents Rendezvous When Tokens Fail,. Tokens and markers have been used successfully to achieve rendezvous when the problem is symmetric, e.g., the network is an anonymous ring and the mobile agents are identical and run the same deterministic algorithm. In this paper, we explore how token failure affects the time required for mobile