Full text
|
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (285kB) | Preview |
A New Implicit Branching Strategy for Exact Maximum Clique
Citation
San Segundo Carrillo, Pablo and Tapia García, Cristóbal (2010). A New Implicit Branching Strategy for Exact Maximum Clique. In: "22nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI", 27/10/2010 - 29/10/2010, Arras, Francia. ISBN 978-1-4244-8817-9.
Description
| Title: | A New Implicit Branching Strategy for Exact Maximum Clique |
|---|---|
| Author/s: |
|
| Item Type: | Presentation at Congress or Conference (Article) |
| Event Title: | 22nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI |
| Event Dates: | 27/10/2010 - 29/10/2010 |
| Event Location: | Arras, Francia |
| Title of Book: | Proceedings of the 22nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI |
| Date: | December 2010 |
| ISBN: | 978-1-4244-8817-9 |
| Subjects: | |
| Freetext Keywords: | maximum clique, branch and bound, exact search, coloring |
| Faculty: | E.U.I.T. Industrial (UPM) |
| Department: | Electrónica, Automática e Informática Industrial [hasta 2014] |
| Creative Commons Licenses: | Recognition - No derivative works - Non commercial |
Abstract
We present a new implicit branching strategy for maximum clique. The new strategy is based in Konj and Janečič's improvement over reference MCR algorithm. It uses a fixed initial non increasing degree vertex ordering at every step of the search, to obtain tighter bounds than MCR on average. We show that the new branching strategy integrates nicely with a natural bit model for the domain. This allows for efficient bound computing using bit masking operations, so that overall improvement in performance is achieved. We present empirical validation over structured and random graphs
More information
| Item ID: | 7907 |
|---|---|
| DC Identifier: | https://oa.upm.es/7907/ |
| OAI Identifier: | oai:oa.upm.es:7907 |
| Official URL: | http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5670057&tag=1 |
| Deposited by: | Memoria Investigacion |
| Deposited on: | 27 Jul 2011 10:28 |
| Last Modified: | 10 Oct 2018 09:03 |
