Memorias de investigación
Communications at congresses:
Watching subgraphs to improve efficiency in maximum clique search.
Year:2013
Research Areas
  • Information technology and adata processing
Information
Abstract
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.
International
Si
Congress
Int. Conf. on Industrial Engineering & Other App. of Applied Intelligent Systems
960
Place
Amsterdam
Reviewers
Si
ISBN/ISSN
1860-949X
Start Date
17/06/2013
End Date
12/06/2013
From page
115
To page
122
Contemporary Challenges and Solutions in Applied Artificial Intelligence,
Participants
Research Group, Departaments and Institutes related
  • Creador: Departamento: Electrónica, Automática e Informática Industrial