跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+0新增论文
+0其中 AI 相关
+0已有论文修订
+92新增 AI 导读

arXiv 最近完成扫描:2026-11-23 01:07 · 全站最近入库:2026-11-21 12:19各信源进度 →

统计口径与数据新鲜度

统计 2026-11-22 03:49 — 2026-11-23 03:49(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-23 01:07最近发现新增版本:2026-11-21 12:19库内论文最新更新时间:2026-11-20 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

29,158 已收录论文24,181 AI 相关8,992 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 3 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-23 01:05(北京时间)
新论文 · v1arXiv:2611.16844

局部性与干扰的交汇:无线电多播中的结构与调度

Locality Meets Interference: Structure and Scheduling in Radio Multicasting

Qin Xin

AI 速读 基于摘要

研究未知位置、允许消息聚合的同步无线电网络中多点到多点多播的调度方案,结合距离二着色、几何信息与随机传输给出多种完成时间界,并讨论扩展与反例。

cs.DC · cs.DS

查看原文摘要

We study multipoint-to-multipoint multicasting in synchronous radio networks with unknown participant locations and unrestricted message aggregation. Let $n$ be the network size, $k$ the number of participants, and $d$ their hop diameter. A supplied distance-two coloring with $C$ colors yields completion within $(C-1)d+1$ slots and at most $nk$ transmissions. In unit disk graphs, coordinates, one-hop neighbor data, and a common degree bound $Δ_0$ suffice for a $15(Δ_0+1)$-color schedule. A known fixed separation bound permits optimal deterministic $Θ(d)$ completion from coordinates alone. Without geometric data, strong selectivity gives $O(d\min\{n,(Δ_0+1)^2\log n\})$ slots when $n$ is known. Independent random transmission gives $O((Δ_0+1)(d+\log(k/η)))$ slots with failure probability at most $η$; for fixed $Δ_0$, this simplifies to $O(d+\log(1/η))$. A star construction shows that the logarithmic term is necessary for this random rule when the degree grows. We extend color schedules to fixed deletions and subgraphs connected over bounded windows of cycles. Separate conditional reductions preserve additive costs under diameter guessing and control parameter-table and cluster preprocessing. Finally, a counterexample shows that pruning and reranking a breadth-first tree can destroy interference-free delivery. For one-hop designated delivery with receiver degree at most $b$, we prove that the optimal schedule length equals the chromatic number of an associated conflict graph and is at most $2b-1$, with matching examples.

新论文 · v1arXiv:2611.08705

Faster Treasure Hunt via Strongly Universal Exploration with Polylogarithmic Overhead

Qin Xin

原文摘要

We study deterministic exploration and delayed-activation treasure hunt in anonymous undirected port-labeled graphs with incoming-port information. From polynomial-time constructible ordinary universal exploration sequences of length \(O(n^c)\) for a fixed regular degree, we construct a single infinite strongly universal exploration sequence with cover time \(O(n^c\log^2n)\). Summable dyadic insertion schedules yield the sharper bound \(O_\eps(n^c\log n(\log\log n)^{1+\eps})\) for every fixed \(\eps>0\), together with refinements at every fixed iterated-logarithm depth. The proof combines reversible excursions, neutral guards and an arbitrary-window argument that treats both orientations simultaneously. For this recurrence, uniform linear expansion is equivalent to convergence of the normalized period sum. Exact counting identities also permit direct instruction access. With a logspace ordinary generator, table-free enumeration of decreasing scale paths computes instruction \(t\) using \(O(\log(t+2))\) working bits and time polynomial in \(t\). The earlier polynomial-slack bounds follow as corollaries. A local cubic simulation extends the treasure-hunt application to arbitrary-degree graphs, with the \(2m\)-vertex replacement size included explicitly in the bound.

cs.CC

版本更新 · v3arXiv:2610.28930

Amplified Pruning and Path Selectors for Deterministic Radio Gossiping

Qin Xin

原文摘要

We study deterministic gossiping in unknown strongly connected directed radio networks with $n$ vertices, $m$ arcs, and distinct identifiers in $[N]$, where $N=n^{\mathcal O(1)}$. Messages are unrestricted and collision detection is unavailable. Our neighborhood-clearing procedure reuses an elected receiver to secure its entire closed in-neighborhood in $\mathcal O(n\log^2n\log\log n)$ rounds. Charging each distinct closed neighborhood once yields $\mathcal O(m\log^2n\log\log n)$ rounds under an explicit degree-concentration condition, for every polynomial identifier range. A complementary adaptive-pruning procedure combines quadratic contraction with completion sensitive to the number of unsecured sources. If $a\ge1$ sources remain at completion entry, permutation selectors reduce the balanced completion budget by a factor of $\log^{2/3}(a+1)$ relative to interleaved path selectors. A geometric execution attains $\widetilde{\mathcal O}(k^2+nτ+\min\{u^2,(nu)^{2/3}\})$ for a path cover of scale $k$, weight $τ$, and $u$ exceptions. For directed graphs with common in- and out-degree $Δ$, the portfolio achieves $\widetilde{\mathcal O}(\min\{n\sqrtΔ,n^2/Δ\})$. Every graph also admits $\widetilde{\mathcal O}(\min\{n^{4/3},N+(mn)^{3/5}\})$ rounds. Only $n,N$ are inputs; degrees, covers, and structural constants are used solely in the analysis. The unrestricted polynomial-identifier density extension remains open.

cs.DS · cs.CC · cs.DC