Memorias de investigación
Ponencias en congresos:
Watching subgraphs to improve efficiency in maximum clique search.
Año:2013
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
This paper describes a new technique referred to as watched subgraphs which improves the performance of BBMC, a leading state of the art exact maximum clique solver (MCP). It is based on watched literals employed by modern SAT solvers for boolean constraint propagation. In efficient SAT algorithms, a list of clauses is kept for each literal (it is said that the clauses 'watch' the literal) so that only those in the list are checked for constraint propagation when a (watched) literal is assigned during search. BBMC encodes vertex sets as bit strings, a bit block representing a subset of vertices (and the corresponding induced subgraph) the size of the CPU register word. The paper proposes to watch two subgraphs of critical sets during MCP search to efficiently compute a number of basic operations. Reported results validate the approach as the size and density of problem instances rise, while achieving comparable performance in the general case.
Internacional
Si
Nombre congreso
Int. Conf. on Industrial Engineering & Other App. of Applied Intelligent Systems
Tipo de participación
960
Lugar del congreso
Amsterdam
Revisores
Si
ISBN o ISSN
1860-949X
DOI
Fecha inicio congreso
17/06/2013
Fecha fin congreso
12/06/2013
Desde la página
115
Hasta la página
122
Título de las actas
Contemporary Challenges and Solutions in Applied Artificial Intelligence,
Esta actividad pertenece a memorias de investigación
Participantes
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Electrónica, Automática e Informática Industrial