Journal
COMBINATORICS PROBABILITY & COMPUTING
Volume 29, Issue 5, Pages 780-806Publisher
CAMBRIDGE UNIV PRESS
DOI: 10.1017/S0963548320000127
Keywords
-
Funding
- NSERC
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available