Mathematical modeling and applications of optimization problems related to search for subgraphs with common structures

• Grant number: 06/01817-7
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: September 01, 2006
• End date: February 14, 2008
• Field of knowledge: Physical Sciences and Mathematics - Computer Science
• Principal Investigator: Cid Carvalho de Souza
• Grantee: Gordana Manic
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

The goal of this project is the study of Combinatorial OptimizationProblems related to subgraph isomorphism and some of its practicalapplications. In particular, we are interested in the investigation ofthe "Maximum Common Subgraph" (MCS) and the "Optimal DatapathMerging" (DPM) problems. In the MCS one looks for a largestsubgraph that iscommon to all elements of a given graph collection, taking into account theattributes of the vertices and the topology of the graphs. Among theapplications of this problem we can mention the pattern recognition andimage processing, computer vision, video indexing, and also thesearch for similarities between molecular structures, which is of greatinterest in Biology and Chemistry. On the other hand, thereconfigurable computing give rise to new architectures in the designof complex digital systems, allowing the designers to take advantageof software flexibility and hardware performance. In this contextarises the DPM which consists in merging parts of the code of anapplication, represented by control/data-flow graphs, to find anequivalent reconfigurable datapath of minimum area. The researchproposed here is focused on theoretical investigations on the facialstructure of the polytopes associated to MCS and DPM and on thedevelopment of exact algorithms based on Integer Programming. We hopethat the results of our research will allow us to solve instancesof size equivalent to that arising from practical applications. (AU)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

CHATAIGNER, F.; MANIC, G.; WAKABAYASHI, Y.; YUSTER, R.. Approximation algorithms and hardness results for the clique packing problem. DISCRETE APPLIED MATHEMATICS, v. 157, n. 7, p. 1396-1406, APR 6 2009. (06/01817-7, 03/09925-5)