English   español  
Por favor, use este identificador para citar o enlazar a este item: http://hdl.handle.net/10261/163016
COMPARTIR / IMPACTO:
Estadísticas
logo share SHARE   Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:
Título

An Exact Algorithm for the Maximum Weight Clique Problem in Large Graphs

AutorJiang, Hua; Li, Chumin; Manyà, Felip
Palabras claveIncremental search
ExactaAlgorithm
Branch-and-bound
Maximum weight clique problem
Fecha de publicación4-feb-2017
EditorAAAI Press
CitaciónProceedings of the Thirty-First AAAI Conference on Artificial Intelligence and the Twenty-Ninth Innovative Applications of Artificial Intelligence Conference, AAAI 2017: 830- 838 (2017)
ResumenWe describe an exact branch-and-bound algorithm for the maximum weight clique problem (MWC), called WLMC, that is especially suited for large vertex-weighted graphs. WLMC incorporates two original contributions: a preprocessing to derive an initial vertex ordering and to reduce the size of the graph, and incremental vertex-weight splitting to reduce the number of branches in the search space. Experiments on representative large graphs from real-world applications show that WLMC greatly outperforms relevant exact and heuristic MWC algorithms, and refute the prevailing hypothesis that exact MWC algorithms are less adequate for large graphs than heuristic algorithms. Copyright © 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
URIhttp://hdl.handle.net/10261/163016
Identificadoresisbn: 978-1-57735-780-3
uri: https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14370
Aparece en las colecciones: (IIIA) Comunicaciones congresos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
accesoRestringido.pdf15,38 kBAdobe PDFVista previa
Visualizar/Abrir
Mostrar el registro completo
 


NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.