Acyclic orientations with path constraints
Rosa M. V. Figueiredo; Valmir C. Barbosa; Nelson Maculan; Cid C. de Souza[1]
- [1] Universidade Estadual de Campinas, Instituto de Computação, Caixa Postal 6176, 13084-971 Campinas - SP, Brazil;
RAIRO - Operations Research - Recherche Opérationnelle (2008)
- Volume: 42, Issue: 4, page 455-467
- ISSN: 0399-0559
Access Full Article
topAbstract
topHow to cite
topReferences
top- [1] K. Aardal, A. Hipolito, C. van Hoesel, B. Jansen, C. Roos, and T. Terlaky, EUCLID CALMA radio link frequency assignment project: A branch-and-cut algorithm for the frequency assignment problem. Technical report, Delft and Eindhoven Universities of Technology, The Netherlands (1995).
- [2] J. Bermond, J. Bond, C. Martin, A. Pekec, and F. Roberts, Optimal orientations of annular networks. J. Interconnection Networks 1 (2000) 21–46.
- [3] J. Bermond, M. Di Ianni, M. Flammini, and S. Perennes, Acyclic orientations for deadlock prevention in interconnection networks, in Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science (1997) 52–64. Zbl0895.68100
- [4] R. Borndörfer, A. Eisenblätter, M. Grötschel, and A. Martin, The orientation model for frequency assignment problems. Technical Report 98-01, Zuse Institute Berlin, Germany (1998). Zbl0895.90090
- [5] R.W. Deming, Acyclic orientations of a graph and chromatic and independence numbers. J. Combin. Theory Ser. B 26 (1979) 101–110. Zbl0331.05110MR525823
- [6] T. Gallai, On directed paths and circuits, in Theory of Graphs edited by P. Erdős and G. Katona, Academic Press, New York, NY (1968) 115–118. Zbl0159.54403MR233733
- [7] M. Grötschel, M. Jünger, and G. Reinelt, Facets of the linear ordering polytope. Math. Program. 33 (1985) 43–60. Zbl0577.05035MR809748
- [8] M. Grötschel, M. Jünger, and G. Reinelt, On the acyclic subgraph polytope. Math. Program. 33 (1985) 28–42. Zbl0577.05034MR809747
- [9] V. Maniezzo and A. Carbonaro, An ants heuristic for the frequency assignment problem. Future Gener. Comput. Syst. 16 (2000) 927–935.
- [10] B. Roy, Nombre chromatique et plus longs chemins d’un graphe, Revue AFIRO 1 (1967) 127–132. Zbl0157.31302MR225683