All Outputs (3)

Graph Labelings Derived from Models in Distributed Computing (2006)
Presentation / Conference Contribution
Chalopin, J., & Paulusma, D. (2006, June). Graph Labelings Derived from Models in Distributed Computing. Presented at WG 2006: Graph-Theoretic Concepts in Computer Science, Bergen, Norway

On-line coloring of H-free bipartite graphs. (2006)
Presentation / Conference Contribution
Broersma, H. J., Capponi, A., & Paulusma, D. (2006, May). On-line coloring of H-free bipartite graphs. Presented at 6th Italian Conference on Algorithms and Complexity (CIAC 2006)., Rome, Italy

We present a new on-line algorithm for coloring bipartite graphs. This yields a new upper bound on the on-line chromatic number of bipartite graphs, improving a bound due to Lovász, Saks and Trotter. The algorithm is on-line competitive on various cl... Read More about On-line coloring of H-free bipartite graphs..

The computational complexity of the parallel knock-out problem (2006)
Presentation / Conference Contribution
Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2006, March). The computational complexity of the parallel knock-out problem. Presented at 7th Latin American Theoretical Informatics Symposium (LATIN 2006), Valdivia, Chile

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for... Read More about The computational complexity of the parallel knock-out problem.