Combinatorics, Graph Theory and Applications. COMBGRAF

Research Projects

Optimization and Extremal Problems in Graph Theory and Combinatorics. Applications to Communication Networks.

Project Reference: MTM2011-28800-C02-01

Main Researcher: Miquel Àngel Fiol Mora

Read more

OPGRACOM

Problemas extremales y de optimización en teoría de grafos y combinatoria: aplicación al análisis y algoritmos de redes de comunicación


Project Reference: MTM2008-06620-C03-01/MTM


Main Researcher: Miquel Àngel Fiol Mora

 

NUMECOVA

Nuevas medidas de conectividad y su valoración en ciertas familias de grafos y digrafos

Project Reference: MTM2005-08990-C02-02

Main Researcher: M. Camino Teófila Balbuena Martínez

Read more

COMBGRAF

Combinatòria, Teoria de Grafs i Aplicacions


Project Reference: 2009SGR1387


Main Researcher: Oriol Serra

Read more

 

GRAAL

Graphs and Algorithms in Communication Networks

Project Reference: COST Action TIST 293

Main Researcher: Xavier Muñoz (2005-2009)


Read more

Extremal Problems in Combinatorics and Graph Theory

Project Reference: MTM2005-08990-C02-01

Main Researcher: Oriol Serra. 2005-2008.

Read more

Grandes redes tolerantes a fallos: nuevos modelos, diseño, análisis y algoritmos

Project Reference: MEC TEC-03575

Main Researcher: Francesc Comellas. 2005-2008.

Read more

Combinatòria, Teoria de Grafs i aplicacions

Project Reference: Grup de Recerca de Qualitat 2005SGR00256

Main Researcher: Oriol Serra (2005-2008)

Read more

Information Management in Distributed Systems: Network Modeling and Design of Algorithms

Project Reference: Spanish Research Council (CICYT, TIC2000-1017 and TIC2001-2171).

Main Researcher: José Fàbrega Canudas. 2001-2004.

Communication Algorithms for All-optical Networks

Project Reference: Joint Action (ACI-98). Generalitat de Catalunya DOGC 2816-29/01/99.

Main Researchers: Francesc Comellas (DMAT, UPC, Catalonia, Spain). Jarda Opatrny (Concordia University, Montreal, Quebec, Canada). 1999.

Communication in Highly Symmetric Networks

Project Reference: Collaborative Research Grant CRG 972241. NATO 1998-2000.

Main Researcher: Francesc Comellas

Optimization of Interconnection Networks: Information Dissemination, Models and Algorithms

Project Reference: Spanish Research Council (CICYT, TIC-97-0963).

Main Researcher: José Fàbrega Canudas. 1997-2000.

Read more

Global Communication Algorithms for Highly Structured Interconnection Networks

Project Reference: Joint Catalonia / Rhone-Alps Action (Generalitat de Catalunya, ACI-96).

Main Researchers: Francesc Comellas (Dep Matematica Aplicada i Telematica, UPC, Catalonia, Spain). Pierre Fraigniaud (Ecole Nationale Superieure de Lyon, France). 1997.

Self-organized Criticality in Interconnection Networks

Project Reference: Joint Spanish-French Action MEC , HF94- 246B.

Main Researchers: Francesc Comellas (Dept. Matemàtica Aplicada i Telemàtica, UPC, Catalonia, Spain). Gilles Zémor (Ecole Nationale de Telecommunications, Paris, France. 1995, 1996.

Efficient Networks for Parallel and Telecommunication Architectures: Structure and Algorithms

Project Reference: Spanish Research Council (CICYT, TIC-94-0592).

Main Researcher: Miquel Àngel Fiol Mora. 1994-1997.

Symmetric Networks, Codes and Parallel Memories

Project Reference: Joint Spanish-French Action MEC , TIC 79 B.

Main Researchers: Oriol Serra (Dept. Matemàtica Aplicada i Telemàtica, UPC, Spain). Gilles Zémor (Ecole Nationale de Telecommunications, Paris, France) 1993.

Efficient Use of Parallel Computers: Architecture, Mapping and Communication

Join research with groups at: CNRS-INRIA Sophia Antipolis, LIP-IMAG Ecole Normale Superieure de Lyon, University of Southampton, Università di Roma "La Sapienza".

Human Capital and Mobility Program (EEC), Coordinator: Burkhard Monien (Universität Paderborn, Germany).

Spanish Responsible: Josep Fàbrega (Dept. Matemàtica Aplicada i Telemàtica, UPC, Barcelona, Spain) 1993-1995.

Interconnection Networks Design and Storage Schemes for Parallel Architectures

Project Reference: Spanish Research Council (CICYT, TIC-90-0712).

Main Researcher: Miquel Àngel Fiol Mora 1990-1993.

Interconnection Networks and Parallel Architectures

Project Reference: Joint Spanish-French Action MEC.

Main Researchers: Jose Luis Andrés Yebra (ETSE Telecomunicacion, Barcelona, Spain). Jean Claude Bermond (Laboratoire de Recherche en Informatique, Orsay, France) 1989-90.

Interconnection Networks, Control and Storage of Data in Distributed Computer Systems

Project Reference: Spanish Research Council (CICYT) PA86-0173.

Main Researcher: Miquel Àngel Fiol Mora. 1987-1990.

Design of Interconnection Networks with Graph Theory

Joint Spanish-French Action MEC 19/137 (1986), MEC 30/302 (1987).

Main Researchers: Jose Luis Andrés Yebra (ETSE Telecomunicacion,Barcelona, Spain). Jean Claude Bermond (Laboratoire de Recherche en Informatique, Orsay, France).

Interconnection Networks for Distributed Computer Systems: Design and Evaluation

Spanish Research Council (CAICYT) project 1180-84.

Main Researcher: Miquel Àngel Fiol Mora. 1985-87

2014SGR1147

Research project.

 

Summaries

 

Optimización y Problemas Extremales en Teoría de Grafos y Combinatoria. Aplicaciones a las Redes de Comunicación.

Los problemas extremales en teoría de grafos y combinatoria consisten en el estudio de configuraciones discretas que optimizan uno o diversos parámetros. En la resolución de esta clase de problemas, este proyecto incluye los de optimización de parámetros métricos de un grafo, de coloración y de etiquetamiento de grafos, de medida de conectividad y fiabilidad, isoperimétricos, de configuraciones en geometrías finitas, de estructuras simétricas, de teselaciones, de diseños de algoritmos y su complejidad computacional, de técnicas del tratamiento de la señal y de teoría aditiva de números. Todos estos problemas se encuentran interrelacionados en el marco del proyecto y están principalmente motivados por aplicaciones en el diseño y análisis de redes de interconexión para sistemas de comunicación y de multiprocesadores. En particular, cabe resaltar las aplicaciones al estudio de redes complejas y sus protocolos de comunicación.
Además de las técnicas de naturaleza combinatoria, el proyecto propone desarrollar la aplicación a problemas extremales de técnicas algebraicas y de análisis espectral (matrices de adyacencia y laplaciana), de análisis de Fourier en grupos abelianos y de métodos polinomiales y probabilísticos en combinatoria. Estas técnicas complementan los métodos combinatorios cercanos a la naturaleza combinatoria de los problemas considerados.
Este proyecto reúne la actividad de un grupo experimentado con más de 25 años de experiencia e internacionalmente reconocido y se inserta en los objetivos de proyectos de ámbito europeo en el área.

 

Optimization and Extremal Problems in Graph Theory and Combinatorics. Applications to Communication Networks.

Extremal problems in Combinatorics and Graph Theory deal with the study of discrete configurations, which optimize one or several parameters. In this framework, the project includes problems related to the optimization of metric parameters of graphs, to coloring and labeling problems, to connectivity and reliability, isoperimetric problems, to configurations in finite geometries, to symmetric structures, to tilings, to algorithm design and its computational complexity, to signal processing techniques, and to additive number theory. All these problems are connected in the framework of the project and are mainly motivated by applications in network design and analysis for communication and multiprocessor systems. In particular, the project considers applications to the study of complex networks and their communication protocols.
The project aims at developing applications to these optimization problems of algebraic techniques and of spectral analysis (adjacency and Laplacian matrices), Fourier analysis in Abelian groups and polynomial and probabilistic methods in combinatorics. These techniques complement the combinatorial methods close to the combinatorial nature of the problems under consideration.
This project gathers the activity of a well-established research group with more than 25 years of experience and with international projection. Its objectives are inserted into European projects the research group is involved with.

NUMECOVA (resumen)

Los principales objetivos del subproyecto que presentamos son los siguientes:

  • Estudiar nuevas medidas de conectividad de grafos que indiquen de forma más precisa las propiedades de las componentes conexas en las que el grafo se descompone cuando fallan nodos y/o ramas.
  • Calcular estos valores de conectividad en diversas familias de grafos: los grafos camino, los grafos secuencia, el producto generalizado de grafos, las jaulas (cages), etc.
  • Extender estos valores de fiabilidad al caso dirigido importante por su aplicación al diseño de redes de interconexión.
  • Contribuir a la resolución de la conjetura que afirma que las jaulas tienen conectividad estándar máxima.

 

NUMECOVA (summary)

The main purposes of this subproject are the following ones:

 

  • To study new graph connectivity measures indicating more precisely the properties of connected components in the decomposition of a graph with faulty nodes and/or edges.
  • The calculation of such connectivity values in various graph families: path graphs, sequence graphs, generalized graph product, cages, etc.
  • To extend this reliability values in the directed case, relevant for its application to interconnection network design.
  • To contribute to the solution of the conjecture claiming that cages have maximum standard connectivity.

COMBGRAF. Combinatòria, Teoria de Grafs i Aplicacions

This is a grant from the Catalan Research Council linked to the label of Excellence Group (Grup de Qualitat). It provides general financing to the Research activity of the group.

Documentation relative to the project

GRAAL (summary)

The acronym GRAAL stands for "Graphs and Algorithms in Communication Networks", which is the title of COST Action TIST 293. GRAAL is an action of the european COST program (European Cooperation in the Field of Scientific and Technical Research) inside of the Telecomunications, Information Science and Tecnology domain (TIST). GRAAL entered into force on september 19th, 2004, to last until october 20th, 2008

The main objective of GRAAL was to elaborate global and solid advances in the design of communication networks by letting experts and researchers with strong mathematical background meet peers specialized in communication networks, and share their mutual experience by forming a multidisciplinary scientific co-operation community.

Extremal Problems in Combinatorics and Graph Theory (summary)

Extremal problems in Combinatorics and Graph Theory deal with the study of discrete configurations which optimize one or several parameters. This project includes problems related to the optimization of diameter and girth of graphs, to coloring and labeling problems, to highly symmetric combinatorial structures, to connectivity and isoperimetric problems, to configurations in finite geometries, to tilings and to additive number theory. All these problems are connected in the framework of the project and are mainly motivated by applications in network design for communication and multiprocessor systems.

The project aims at developing applications to these extremal problems of techniques of spectral analysis, Fourier analysis in abelian groups and polynomial methods in combinatorics, like Redei polynomials or the Combinatorial Nullstellensatz. These techniques complement the combinatorial methods close to the combinatorial nature of the problems under consideration.

The project gathers the activity of a well established research group with international projection and its objectives are inserted into European projects the research group is involved with.

 

Grandes redes tolerantes a fallos: nuevos modelos, diseño, análisis y algoritmos

Large Fault-tolerant Networks: New Models, Design, Analysis and Algorithms (summary)

One main characteristic of our technological society is the ubiquitous presence of large networks like the WWW, phone networks, power grids, transportation systems and even social, biological and data networks. We have recently started to understand their basic characteristics: all are complex networks with a low diameter (maximum distance between any pair of nodes ), high clustering, the networks are usually scale-free and very often they have evolved without a centralized planning. In parallel to their growth it has increased enormously the vulnerability with important consequences as shown, for example, by the blackouts of America and Europe in 2003, the shutdown of the WWW (2002), or the massive breakdown of the computer network of the Department of Work and Pensions of the United Kingdom (2004). This fragility shows the importance of a better understanding of these large structures through new approaches. Thus, in this research project we will develop new models and algorithms to quantify the risk to failures and to allow the design of methods to diminish it. The objectives include the development of new tools and mathematical measures (based on graph theoretical methods and including spectral and probabilistic techniques), the modelling and study of the main characteristics of large real networks (their clustering, existence of hubs, hierarchical structure, motifs, etc), the design of agent based algorithms to detect characteristics associated to the failures (connectivity, coherence, synchronization) and the development of new basic fault tolerant communication schemes.

 

Combinatòria, Teoria de Grafs i Aplicacions (resum)

L'objectiu genèric del grup és l'aplicació de la teoria de grafs i les estructures combinatòries en general a l'anàlisi i disseny de xarxes d'interconnexió. En aquest objectiu hi conflueixen tècniques de teoria de grafs, combinatòria algebraica i enumerativa, optimització combinatòria, algorísmica, estructures aleatòries i geometria discreta. Els temes bàsics són el disseny de topologies per xarxes d'interconnexió, fiabilitat i vulnerabilitat, algorismes de comunicació i de difusió de la informació, i els aspectes teòrics que se'n deriven en la teoria de grafs i la combinatòria.

Combinatorics, Graph Theory and Applications (summary)


The general purpose of the group is the application of graph theory and combinatorial structures to the analysis and design of interconnection networks. Various techniques may be used: graph theory, algebraic and enumerative combinatorics, combinatorial optimization, algorithmics, random structures and discrete geometry. Fundamental subjects are the design of interconnection network topologies, reliability and vulnerability, communication and information dissemination algorithms, and the theoretical aspects derived from them in graph theory and combinatorics.

Optimization of Interconnection Networks: Information Dissemination, Models and Algorithms (summary)

The design of interconnection networks arises as an important problem in Computer Science and Telecommunication Engineering. The optimization of interconnection structures and information dissemination schemes for multiprocessor and distributed systems leads to many combinatorial problems which are the main aim of this project, and constitute the research activity of the group behind this proposal. In this context, the main objectives of the project are:

  1. The design of interconnection networks in order to optimize its perfomance and basic parameters: message delay, fault tolerance, simmetry, workload distribution, local and global communication algorithms and security aspects of the communication problems.
  2. The design of new tools for the analysis of network parameters: Spectral analysis, decomposition methods, connectivity measures, coloring techniques, genetic algorithms and heuristics.

 

2014SGR1147

Research project.