ﻻ يوجد ملخص باللغة العربية
We prove that any $n$-node graph $G$ with diameter $D$ admits shortcuts with congestion $O(delta D log n)$ and dilation $O(delta D)$, where $delta$ is the maximum edge-density of any minor of $G$. Our proof is simple, elementary, and constructive - featuring a $tilde{Theta}(delta D)$-round distributed construction algorithm. Our results are tight up to $tilde{O}(1)$ factors and generalize, simplify, unify, and strengthen several prior results. For example, for graphs excluding a fixed minor, i.e., graphs with constant $delta$, only a $tilde{O}(D^2)$ bound was known based on a very technical proof that relies on the Robertson-Seymour Graph Structure Theorem. A direct consequence of our result is that many graph families, including any minor-excluded ones, have near-optimal $tilde{Theta}(D)$-round distributed algorithms for many fundamental communication primitives and optimization problems including minimum spanning tree, minimum cut, and shortest-path approximations.
A class of graphs is $chi$-bounded if there exists a function $f:mathbb Nrightarrow mathbb N$ such that for every graph $G$ in the class and an induced subgraph $H$ of $G$, if $H$ has no clique of size $q+1$, then the chromatic number of $H$ is less
We investigate graph problems in the following setting: we are given a graph $G$ and we are required to solve a problem on $G^2$. While we focus mostly on exploring this theme in the distributed CONGEST model, we show new results and surprising conne
We give polynomial-time approximation schemes for monotone maximization problems expressible in terms of distances (up to a fixed upper bound) and efficiently solvable in graphs of bounded treewidth. These schemes apply in all fractionally treewidth-
We study the problem of online graph exploration on undirected graphs, where a searcher has to visit every vertex and return to the origin. Once a new vertex is visited, the searcher learns of all neighboring vertices and the connecting edge weights.
Best match graphs (BMGs) are vertex-colored digraphs that naturally arise in mathematical phylogenetics to formalize the notion of evolutionary closest genes w.r.t. an a priori unknown phylogenetic tree. BMGs are explained by unique least resolved tr