ﻻ يوجد ملخص باللغة العربية
Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no online edge-coloring algorithm can edge color a graph optimally. Indeed, their work, titled the greedy algorithm is optimal for on-line edge coloring, shows that the competitive ratio of $2$ of the naive greedy algorithm is best possible online. However, their lower bound required bounded-degree graphs, of maximum degree $Delta = O(log n)$, which prompted them to conjecture that better bounds are possible for higher-degree graphs. While progress has been made towards resolving this conjecture for restricted inputs and arrivals or for random arrival orders, an answer for fully general emph{adversarial} arrivals remained elusive. We resolve this thirty-year-old conjecture in the affirmative, presenting a $(1.9+o(1))$-competitive online edge coloring algorithm for general graphs of degree $Delta = omega(log n)$ under vertex arrivals. At the core of our results, and of possible independent interest, is a new online algorithm which rounds a fractional bipartite matching $x$ online under vertex arrivals, guaranteeing that each edge $e$ is matched with probability $(1/2+c)cdot x_e$, for a constant $c>0.027$.
The Road Coloring Theorem states that every aperiodic directed graph with constant out-degree has a synchronized coloring. This theorem had been conjectured during many years as the Road Coloring Problem before being settled by A. Trahtman. Trahtmans
Vizings celebrated theorem asserts that any graph of maximum degree $Delta$ admits an edge coloring using at most $Delta+1$ colors. In contrast, Bar-Noy, Naor and Motwani showed over a quarter century that the trivial greedy algorithm, which uses $2D
We study a variation of the classical Shortest Common Superstring (SCS) problem in which a shortest superstring of a finite set of strings $S$ is sought containing as a factor every string of $S$ or its reversal. We call this problem Shortest Common
We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q>1 and a graph G, the goal is to find a coloring of the edges of G with the maximu
We consider a decentralized graph coloring model where each vertex only knows its own color and whether some neighbor has the same color as it. The networking community has studied this model extensively due to its applications to channel selection,