Previous | 
Home
Section: Scientific Foundations
Scientific Foundations
The project develops tools and theory in the following domains: Discrete Mathematics (in particular Graph Theory), Algorithmics, Combinatorial Optimization and Simulation.
Typically, a telecommunication network (or an interconnection
network) is modeled by a graph. A vertex may represent either a
processor or a router or any of the following: a switch, a radio
device, a site or a person. An edge (or arc) corresponds to a
connection between the elements represented by the vertices (logical
or physical connection). We can associate more information both to
the vertices (for example what kind of switch is used, optical or
not, number of ports, equipment cost) and to the edges (weights
which might correspond to length, cost, bandwidth, capacity) or
colors (modeling either wavelengths or frequencies or failures) etc.
Depending on the application, various models can be defined and have
to be specified. This modeling part is an important task. To solve
the problems, we manage, when possible, to find polynomial
algorithms. For example, a maximum set of disjoint paths between two
given vertices is by Menger's theorem equal to the minimum
cardinality of a cut. This problem can be solved in polynomial time
using graph theoretic tools or flow theory or linear programming. On
the contrary, determining whether in a directed graph there exists a
pair of disjoint paths, one from
Graph coloring is an example of concept which appears in various contexts: WDM networks where colors represent wavelengths, radio networks where colors represent frequencies, fault tolerance where colors represent shared risk resource groups, and scheduling problems. Another tool concerns the development of new algorithmic aspects like parameterized algorithms.