Biclique completion problems for multicast network design
| Autor: | Philippe Chrétienne, Nathalie Faure, Francis Sourd, Eric Gourdin |
|---|---|
| Přispěvatelé: | Recherche Opérationnelle (RO), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2007 |
| Předmět: |
Theoretical computer science
Linear programming Multicast Applied Mathematics Column generation 020206 networking & telecommunications 02 engineering and technology Complete bipartite graph Telecommunications network Session (web analytics) Theoretical Computer Science Integer linear programming Computational Theory and Mathematics Multicast session aggregation 0202 electrical engineering electronic engineering information engineering Biclique partitioning [INFO]Computer Science [cs] 020201 artificial intelligence & image processing Xcast Integer programming Mathematics |
| Zdroj: | Discrete Optimization Discrete Optimization, 2007, 4 (3-4), pp.360-377. ⟨10.1016/j.disopt.2007.09.005⟩ Discrete Optimization, Elsevier, 2007, 4 (3-4), pp.360-377. ⟨10.1016/j.disopt.2007.09.005⟩ |
| ISSN: | 1572-5286 1873-636X |
| DOI: | 10.1016/j.disopt.2007.09.005 |
| Popis: | International audience; This paper considers the problem of aggregating several multicast sessions. A multicast session is defined as a subset of clients requiring the same information. Besides, each client can require several multicast sessions. A telecommunication network cannot manage many multicast sessions at the same time. It is hence necessary to group the sessions into a limited number of clusters. The problem then consists in aggregating the sessions into clusters to limit the number of unnecessary information sent to clients. The strong relationship of the problems with biclique problems in bipartite graph is established. We then model the problems using integer quadratic and linear programming formulations. We investigate some properties to strengthen the models. Several algorithms are provided and compared with a series of numerical experiments. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect