Resumen:
Dados dos grafos G y H con igual cantidad de vértices, el problema de encontrar un subgrafo común a ambos grafos que maximice la cantidad de aristas se denomina problema de subgrafo máximo por aristas (MCESP). Una definición equivalente es encontrar una asignación : VG −→ VH uno a uno que maximize la cardinalidad de f, donde la cardinalidad se dene como |{uv ∈ EG : f(u) f(v) ∈ EH}|. Se sabe que este problema es NP-completo en el caso general. La mayoría de los trabajos relacionados con el MCESP hasta el día de hoy se centraron en obtener algoritmos eficientes para computar asignaciones de cardinalidades aceptables. Dado el escaso estudio de la complejidad del MCESP en la literatura nos proponemos contribuir a dicha área. En este trabajo exploramos el comportamiento de la complejidad del MCESP cuando los grafos de entrada son restringidos a diversas familias, centrándonos en distinguir los casos NP-completos de los polinomiales. Algunas de las familias estudiadas son grafos bipartitos, split, de intervalos, cografos, árboles y grillas. Por otro lado, relacionamos el MCESP con el problema de isomorfismo de grafos y la clase de complejidad GI. Por último estudiamos aspectos generales del comportamiento de las asignaciones y asignaciones óptimas.
Abstract:
Given two graphs G and H with the same number of vertices, the problem of finding a common subgraph of both graphs that maximizes the number of edges is called maximum common-edge subgraph problem (MCESP). An equivalent definition is to nd a 1-1 mapping f : VG −→ VH that maximizes the cardinality of f, where the cardinality is defined as |{uv ∈ EG : f(u) f(v) ∈ EH}|. This problem is known to be NP-complete in the general case. Most of the works related with MCESP up to day were aimed to obtain efficient algorithms for computing mappings with reasonable cardinality. Given the limited study of the MCESP complexity in the literature, we propose ourselves to contribute to this area. In this work we explore the behavior of MCESP complexity when the input graphs are restricted to diverse families, focusing on distinguishing the NP-complete cases from polynomial cases. Some of the studied families are bipartite, split, interval, cographs, trees and grid graphs. On the other hand we relate the MCESP with the graph isomorphism problem and the GI (Script Capital? Gothic? complexity class. Finally we study general behavioral aspects of mappings and optimal mappings.
Citación:
---------- APA ----------
Vassiliev, Saveliy. (2013). Exploring the complexity boundary of the maximum common edge subgraph problem. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000687_Vassiliev
---------- CHICAGO ----------
Vassiliev, Saveliy. "Exploring the complexity boundary of the maximum common edge subgraph problem". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2013.https://hdl.handle.net/20.500.12110/seminario_nCOM000687_Vassiliev
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000687_Vassiliev.pdf
Distrubución geográfica
