Melanoma
发表于 2025-3-23 11:56:04
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
发表于 2025-3-23 17:38:08
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
使成波状
发表于 2025-3-23 21:13:10
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
宽大
发表于 2025-3-23 22:52:26
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
啜泣
发表于 2025-3-24 04:24:50
http://reply.papertrans.cn/88/8800/879958/879958_15.png
表两个
发表于 2025-3-24 07:27:09
http://reply.papertrans.cn/88/8800/879958/879958_16.png
Picks-Disease
发表于 2025-3-24 11:43:16
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
净礼
发表于 2025-3-24 16:41:47
http://reply.papertrans.cn/88/8800/879958/879958_18.png
Bravado
发表于 2025-3-24 20:52:01
http://reply.papertrans.cn/88/8800/879958/879958_19.png
鲁莽
发表于 2025-3-25 01:32:36
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