New complexity results for time-constrained dynamical optimal path problems.
New lower bounds on the weighted chromatic number of a graph
In this paper we present theoretical and algorithmic results for the computation of lower bounds on the chromatic number of a weighted graph. In particular, we study different ways of a possible improvement of the lower bound offered by a maximum weighted clique. Based on our findings we devise new algorithms and show their performance on random graphs.
New results on generalized graph coloring.
NP-completeness of minimal width unordered tree layout.
NP-hardness results for intersection graphs