{"id":92041,"date":"2009-04-03T00:00:00","date_gmt":"2009-04-03T00:00:00","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/efficient-algorithms-for-graph-isomorphism-testing\/"},"modified":"2009-04-03T00:00:00","modified_gmt":"2009-04-03T00:00:00","slug":"efficient-algorithms-for-graph-isomorphism-testing","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/informatica\/efficient-algorithms-for-graph-isomorphism-testing\/","title":{"rendered":"Efficient algorithms for graph isomorphism testing"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Jos\u00e9 Luis Lopez Presa <\/strong><\/h2>\n<p>: el problema del isomorfismo de grafos ha sido estudiado por los cient\u00edficos durante mucho tiempo, desde distintos puntos de vista. Es interesante desde el punto de vista te\u00f3rico, puesto que no se sabe si es np-copleto o no. Dado que hay multitud de problemas que pueden reducirse al isomorfismo de grafos, establecer completamente su complejidad, permitir\u00eda extrapolar el resultado a todos los problemas que pueden reducirse a \u00e9l. Adem\u00e1s, tiene mucho inter\u00e9s pr\u00e1ctico por las aplicaciones que tiene en campos tan diversos como qu\u00edmica, visi\u00f3n artificial o miner\u00eda de datos. Los algoritmos pr\u00e1cticos para el isomorfismo de grafos suelen, o bien tratar de encontrar el isomorfismo mediante un algoritmo cl\u00e1sico de vuelta atr\u00e1s ayudado por una poda heur\u00edstica, enfoque que tiene problemas cuando los grafos tienen muchas simetr\u00edas (automorfismos), o bien calculado un etiquetado can\u00f3nico de los v\u00e9rtices, para lo que es necesario calcualr el grupo de automorfismo completo de los grafos, lo que puede resultar mucho m\u00e1s duro que encontrar el isomorfismo entre ellos. el objetivo de la tesis es dise\u00f1ar y programar un algoritmo para determinar el isomorfismo de grafos, que sea r\u00e1pido en la pr\u00e1ctica, que tenga un comportamiento uniforme, y que no necesite para ello calcular completamente el grupo de automorfismo de los grafos. Para evaluar el rendimiento pr\u00e1ctico de nuestro algoritmo, lo hemos codificado en c y lo hemos comparado con otros dos algoritmos. De una parte vf2, como ejemplo de algoritmo heur\u00edstico, que para ciertas familias de grafos tiene un comportamiento muy bueno, y nauty, que el el prpograma de isomorfismo de grafos por excelencia, que usa el otro enfoque y es hoy por hoy el referente mundial, aunque es conocido que tiene un comportamiento exponencial para ciertas familias de grafos. Hoy en d\u00eda hay algunas bater\u00edas de pruebas que incluyen diversas familias de grafos, pero que no cubren todos tipos de grafos que quer\u00edamos tratar. Por ello, hemos generado una bater\u00eda de pruebas con nuevas familias de grafos, tanto para probar casos positivos como negativos de isomorfismo. nuestro algoritmo trabaja en tres fases. En la primera realiza un an\u00e1lisis de los grafos y genera una estructura de datos (secuencia de particiones) para cada uno de ellos. A continuaci\u00f3n busca automorfismos en los grafos a partir de esta secuencia de particiones, y por \u00faltimo, se toma la secuencia de particiones de uno de los grafos como patr\u00f3n, y se trata de generar una secuencia de particiones equivalente para el otro grafo. Los grafos son isomorfos si y s\u00f3lo si es posible reproducir esta estructura de datos para el otro grafo. Este enfoque es novedoso y, en las pruebas que hemos realizado con nuestra bater\u00eda de grafos, hemos comprobado que tiene un comportamiento uniforme con todas las familias de grafos consideradas, y que en algunos casos tiene un rendimiento similar a los otros algoritmos, mientras que en otros los desborda completamente. Los casos m\u00e1s significativos son aquellos en los que nauty y vf2 tienen un comportamiento exponencial, mientras que nuestro algoritmo conauto tiene un comportamiento polin\u00f3mico. Este ocurre con una familia de grafos contruida por takunary miyazaki a partir de una contrucci\u00f3n de martin f\u00ed\u00bcrer, y con grafos uni\u00f3n (por ejemplo, grafos generados mediante la uni\u00f3n disjunta de componentes sencillas). hemos demostrado la correcci\u00f3n de nuestro algoritmo y hemos analizado su complejidad espacial y temporal. Probamos que tiene una complejidad espacial de 0(n2) palabras para grafos de n v\u00e9rtices. En el caso mejor, tiene una complejidad temporal 0(n2), y con alta probabilidad es polin\u00f3mico.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Efficient algorithms for graph isomorphism testing<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Efficient algorithms for graph isomorphism testing <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Jos\u00e9 Luis Lopez Presa <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Rey juan carlos<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 04\/03\/2009<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li>Antonio Fernandez Anta<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: Mar\u00eda  jose Serna iglesias <\/li>\n<li>roberto Mu\u00f1oz izquierdo (vocal)<\/li>\n<li>Manuel Abellanas oar (vocal)<\/li>\n<li>Jes\u00fas Garc\u00eda l\u00f3pez de lacalle (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Jos\u00e9 Luis Lopez Presa : el problema del isomorfismo de grafos ha sido estudiado por los cient\u00edficos [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[37303,13880,36610],"tags":[73250,30717,190532,10832,105628,50518],"class_list":["post-92041","post","type-post","status-publish","format-standard","hentry","category-heuristica","category-informatica","category-rey-juan-carlos","tag-antonio-fernandez-anta","tag-jesus-garcia-lopez-de-lacalle","tag-jose-luis-lopez-presa","tag-manuel-abellanas-oar","tag-maria-jose-serna-iglesias","tag-roberto-munoz-izquierdo"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/92041","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=92041"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/92041\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=92041"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=92041"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=92041"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}