Name
Abstract | ||
|---|---|---|
We give an efficient algorithm that, given a graph G and a partition V-1,..., V-m of its vertex set, finds either an independent transversal (an independent set {nu(1),..., nu(m)} in G such that nu 1 is an element of V-1 for each i), or a subset B of vertex classes such that the subgraph of G induced by boolean OR B has a small dominating set. A non-algorithmic proof of this result has been known for a number of years and has been used to solve many other problems. Thus we are able to give algorithmic versions of many of these applications, a few of which we describe explicitly here. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1017/S0963548320000127 | COMBINATORICS PROBABILITY & COMPUTING |
DocType | Volume | Issue |
Journal | 29 | 5 |
ISSN | Citations | PageRank |
0963-5483 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alessandra Graf | 1 | 0 | 0.34 |
| P. E. Haxell | 2 | 212 | 26.40 |