Navegar

Colección

Datos Estadísticas

Artículo

La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Point-to-Multipoint systems are one kind of radio systems supplying wireless access to voice/data communication networks. Capacity constraints typically force the reuse of frequencies but, on the other hand, no interference must be caused thereby. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-Hard, and there exist no polynomial time algorithms with a guaranteed quality. In order to apply cutting plane methods to this problem, the associated chromatic scheduling polytopes must be studied. These polytopes have interesting theoretical properties. In this work, we present a characterization of the extreme points of chromatic scheduling polytopes, which enables to prove combinatorial equivalence properties. © 2005 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Combinatorial equivalence of Chromatic Scheduling Polytopes
Autor:Marenco, J.; Wagler, A.
Filiación:Departamento de Computación, FCEN, Universidad de Buenos Aires, Pabellón I, (1428) Buenos Aires, Argentina
Konrad-Zuse-Zentrum für Informationstechik Berlin, Takustr. 7, 14195 Berlin, Germany
Palabras clave:combinatorial equivalence; polyhedral combinatorics
Año:2004
Volumen:18
Página de inicio:177
Página de fin:180
DOI: http://dx.doi.org/10.1016/j.endm.2004.06.028
Título revista:Electronic Notes in Discrete Mathematics
Título revista abreviado:Electron. Notes Discrete Math.
ISSN:15710653
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v18_n_p177_Marenco

Referencias:

  • de Werra, D., Gay, Y., Chromatic scheduling and frequency assignment (1994) Discrete Appl. Math., 49, pp. 165-174
  • de Werra, D., Hertz, A., Consecutive colorings of graphs (1988) ZOR, 32, pp. 1-8
  • Kubale, M., Interval vertex-coloring of a graph with forbidden colors (1989) Discrete Math., 74, pp. 125-136;

Citas:

---------- APA ----------
Marenco, J. & Wagler, A. (2004) . Combinatorial equivalence of Chromatic Scheduling Polytopes. Electronic Notes in Discrete Mathematics, 18, 177-180.
http://dx.doi.org/10.1016/j.endm.2004.06.028
---------- CHICAGO ----------
Marenco, J., Wagler, A. "Combinatorial equivalence of Chromatic Scheduling Polytopes" . Electronic Notes in Discrete Mathematics 18 (2004) : 177-180.
http://dx.doi.org/10.1016/j.endm.2004.06.028
---------- MLA ----------
Marenco, J., Wagler, A. "Combinatorial equivalence of Chromatic Scheduling Polytopes" . Electronic Notes in Discrete Mathematics, vol. 18, 2004, pp. 177-180.
http://dx.doi.org/10.1016/j.endm.2004.06.028
---------- VANCOUVER ----------
Marenco, J., Wagler, A. Combinatorial equivalence of Chromatic Scheduling Polytopes. Electron. Notes Discrete Math. 2004;18:177-180.
http://dx.doi.org/10.1016/j.endm.2004.06.028