Utorak, 18.03.2008. u 14:15, sala 305, MI BG:

Nebojsa Gvozdenovic, Ekonomski fakultet, Subotica
APPROXIMATING THE STABILITY NUMBER AND THE CHROMATIC NUMBER OF A GRAPH VIA SEMIDEFINITE PROGRAMMING

Abstract: We introduce a special operator $\Psi$ which maps upper bounds for the stability number to lower bounds for the chromatic number. As an application, we prove that there is no polynomial time computable graph parameter nested between the fractional chromatic and the chromatic number of a graph, unless P=NP.

Utorak, 25.03.2008. u 14:15, sala 305, MI BG:

Tatjana Davidovic, Dragos Cvetkovic, Matematicki institut SANU, Beograd CHARACTERIZATION OF MULTIPROCESSOR INTERCONNECTION NETWORKS USING GRAPH THEORY

Abstract: Homogeneous multiprocessor systems are usually modelled by undirected graphs. Vertices of these graphs represent the processors, while edges denote the connection links between adjacent processors. Let $G$ be a graph with diameter $D$, maximum vertex degree $\Delta$, the largest eigenvalue $\lambda_1$ and $m$ distinct eigenvalues. The products $m\Delta$ and $(D+1)\lambda_1$ are called the tightness of $G$ of the first and second type, respectively. In the recent literature it was suggested that graphs with a small tightness of the first type are good models for the multiprocessor interconnection networks. We study these and some other types of tightness and some related graph invariants and demonstrate their usefulness in the analysis of multiprocessor interconnection networks. Tightness values for graphs of some standard interconnection networks are determined. We also present some fact showing that the tightness of the second type is the relevant graph invariant. We prove that the number of connected graphs with a bounded tightness is finite.

RUKOVODIOCI SEMINARA

Vera Kovačević-Vujčić
Milan Dražić