跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+479新增论文
+361其中 AI 相关
+64已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-16 01:34 · 全站最近入库:2026-11-16 21:56各信源进度 →

统计口径与数据新鲜度

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

最近完成检查:2026-11-16 01:34最近发现新增版本:2026-11-16 21:56库内论文最新更新时间:2026-11-14 02:59

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

23,827 已收录论文19,941 AI 相关6,922 有修订112 HF 社区发现

浏览论文库

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

找到 3 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-16 01:33(北京时间)
版本更新 · v6arXiv:2603.29629

On graph products and multi-word-representability

Benny George Kenkireth, Gopalan Sajith, Sreyas Sasidharan

原文摘要

The multi-word-representation number $μ(G)$ is the minimum number of word-representable graphs whose union is $G$. We investigate $μ(H)$ for graph products $H$ obtained from $G_1$ and $G_2$ via six fundamental products: lexicographic, Cartesian, rooted, corona, tensor, and strong. We prove $μ(H) = \max\{μ(G_1), μ(G_2)\}$ for Cartesian and rooted products. For the corona product, we show $\max\{μ(G_1), μ(G_2)\} \le μ(H) \le \max\{μ(G_1), μ(G_2)\} + 1$, and show that the lower bound is tight when $μ(G_1) > μ(G_2)$ or $G_2$ admits a covering by $μ(G_2)$ word-representable graphs, one of which is a comparability graph. For the lexicographic product, we show $\max\{μ(G_1), μ(G_2)\} \le μ(H) \le μ(G_1) + μ(G_2)$, and show that the lower bound is tight when $\mathrm{cov}_{\mathrm{comp}}(G_2) \le \max\{μ(G_1), μ(G_2)\}$. We provide logarithmic bounds for tensor and strong products. We prove $G^{[k]}$ is word-representable if and only if $G$ is a comparability graph. We establish bounds $μ(G^{[k]}) \le \mathrm{cov}_{\mathrm{comp}}(G)$ and $μ(G^{[k]}) \le k$ for non-comparability word-representable graphs. Using lexicographic powers, we obtain the sublinear bound $τ(n) \le n^{\log_8 6+ε}$ for the extremal function $τ(n)$. Finally, we address the Word-representable Bipartition (WB) problem, proving a negative answer for $n \geq 433$: showing that for every such $n$, there exists a graph of order $n$ that cannot be vertex-partitioned into two word-representable induced subgraphs.

math.CO · cs.DM

版本更新 · v5arXiv:2502.06979

Word-representability and comparability: Minimal forbidden induced subgraphs and cover number bounds

Benny George Kenkireth, Gopalan Sajith, Sreyas Sasidharan

原文摘要

Word-representable graphs, characterized by the existence of a semi-transitive orientation, form a well-studied class of graphs. Comparability graphs form another well-studied class and constitute a subclass of word-representable graphs. Both classes are hereditary and admit characterizations in terms of minimal forbidden induced subgraphs. While the minimal forbidden induced subgraphs for comparability graphs are completely characterized, the corresponding characterization for word-representable graphs remains open. In this paper, we precisely determine which minimal non-comparability graphs are also minimal non-word-representable graphs by classifying minimal non-comparability graphs according to whether they are word-representable. As a consequence, we provide a complete description of minimal non-word-representable graphs containing an all-adjacent vertex. We also address an open problem posed by Kenkireth et al.\ concerning the cover number of word-representable graphs by comparability graphs. We demonstrate the existence of word-representable graphs on $n$ vertices whose cover number by comparability graphs is $Ω(\log n)$, which establishes that the universal $O(\log n)$ upper bound is asymptotically tight for the class of word-representable graphs. For triangle-free circle graphs, we establish that the cover number by comparability graphs is at most $3$ and demonstrate that this bound is tight. More generally, we show that for any circle graph $G$ with clique number $ω(G)$, the cover number by comparability graphs is bounded by $O(\log ω(G))$. Finally, we identify four subclasses of word-representable graphs for which the cover number by comparability graphs of every graph in these classes is at most $2$.

cs.DM

新论文 · v1arXiv:2611.04914

Sorting in PRAM, Parallel Comparison Model and Parallel External Memory Model

Gopalan Sajith, Manas Kumar Panda, Ranajit Senko

原文摘要

We study the problem of sorting on the Parallel Random Access Machine (PRAM), Parallel Comparison Model (PCM) and Parallel External Memory Model (PEM). On PRAM, we present a Concurrent Read Exclusive Write algorithm that runs in $O(\log n)$ time with $n$ processors; our algorithm is very different from Cole's Merge Sort. On PCM, we present the first optimal algorithm for sorting after AKS; our algorithm runs in $O(\log n/\logα)$ comparison rounds with $nα$ processors, for $1\leqα\leq n$. On PEM, we present a Concurrent Read Exclusive Write algorithm that sorts $N$ elements in $O\left(\log\frac{N}{B}\right)$ I/O rounds with $p\geq \frac{N}{B}$ processors.

cs.DS