期刊
ACM TRANSACTIONS ON ALGORITHMS
卷 18, 期 1, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3474057
关键词
Independent transversal; strong colouring
资金
- NSERC
This article presents a new randomized algorithm that is more widely applicable and efficient in solving problems related to the strong chromatic number of graphs, closing the gap between existing bounds and algorithmic proofs.
An independent transversal (IT) in a graph with a given vertex partition is an independent set consisting of one vertex in each partition class. Several sufficient conditions are known for the existence of an IT in a given graph and vertex partition, which have been used over the years to solve many combinatorial problems. Some of these IT existence theorems have algorithmic proofs, but there remains a gap between the best existential bounds and the bounds obtainable by efficient algorithms. Recently, Graf and Haxell (2018) described a new (deterministic) algorithm that asymptotically closes this gap, but there are limitations on its applicability. In this article, we develop a randomized algorithm that is much more widely applicable, and demonstrate its use by giving efficient algorithms for two problems concerning the strong chromatic number of graphs.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据