> Merkliste Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp: E-Artikel Titel: Iterative coloring extension of a maximum clique Beteiligte: Caramia, Massimiliano; Dell'Olmo, Paolo Erschienen: Wiley, 2001 Erschienen in: Naval Research Logistics (NRL), 48 (2001) 6, Seite 518-550 Sprache: Englisch DOI: 10.1002/nav.1033 ISSN: 0894-069X; 1520-6750 Schlagwörter: Management Science and Operations Research ; Ocean Engineering ; Modeling and Simulation Entstehung: Anmerkungen: Beschreibung: AbstractIn this paper we present an improved branch and bound algorithm for the vertex coloring problem. The idea is to try to extend the coloring of a maximum clique to its adjacent vertices. If this succeeds, its successive neighbors are considered; in case of failure (i.e., in the case the initial colors are not sufficient), working on the subgraph induced by the maximum clique and its neighborhood, the lower bound is improved by seeking for an optimal coloring of this subgraph by branch and bound. The process is repeated iteratively until the whole graph is examined. The iterative scheme exploits a further lower bound obtained by integrating a simple algorithm into the maximum clique search, and a new method to compute upper bounds on subgraphs. Furthermore, a new branching rule and a method for the selection of the initial maximum clique are presented. Extensive computational results and comparisons with existing exact coloring algorithms on random graphs and benchmarks are given. © 2001 John Wiley & Sons, Inc. Naval Research Logistic 48: 518–550, 2001