This paper studies how to use fast matrix multiplication to speed up query processing. As
observed, computing a two-table join and then projecting away the join attribute is …

We study the fine-grained complexity of graph connectivity problems in unweighted
undirected graphs. Recent development shows that all variants of edge connectivity …

In the $ k $-Disjoint Shortest Paths ($ k $-DSP) problem, we are given a weighted graph $ G
$ on $ n $ nodes and $ m $ edges with specified source vertices $ s_1,\dots, s_k $, and …

In an $ m $-edge host graph $ G $, all triangles can be listed in time $ O (m^{1.5}) $[Itai,
Rodeh'78], and all $ k $-cycles can be listed in time $ O (m^{2-1/{\lceil k/2\rceil}}+ t) $ where …

For vertices u and v of an n-vertex graph G, a uv-trail of G is an induced uv-path of G that is
not a shortest uv-path of G. Berger, Seymour, and Spirkl [Discrete Mathematics 2021] gave …

Klee's measure problem (computing the volume of the union of $ n $ axis-parallel boxes in
$\mathbb {R}^ d $) is well known to have $ n^{\frac {d}{2}\pm o (1)} $-time algorithms …

判斷一張圖中是否包含某種導出子圖, 在圖論以及演算法領域的許多重要成果都扮演了重要角色
. 其中一個具有高度代表性的例子是[完美圖的辨識問題], 也就是判定一張圖是否符合[每個導出 …

Let u and v be vertices in a connected graph G=(V, E). For any integer k such that 0≤ k≤ dG
(u, v), the k-slice Sk (u, v) contains all vertices x on a shortest uv-path such that dG (u, x)= k …

A popular way to define or characterize graph classes is via forbidden subgraphs or
forbidden minors. These characterizations play a key role in graph theory, but they rarely …