{"id":15575,"date":"2018-03-09T09:02:47","date_gmt":"2018-03-09T09:02:47","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/problemas-de-conexiones-ortogonales\/"},"modified":"2018-03-09T09:02:47","modified_gmt":"2018-03-09T09:02:47","slug":"problemas-de-conexiones-ortogonales","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/matematicas\/problemas-de-conexiones-ortogonales\/","title":{"rendered":"Problemas de conexiones ortogonales"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Jos\u00e9 Ramon Portillo Fernandez <\/strong><\/h2>\n<p>El \u00e1rea de investigaci\u00f3n sobre dibujos de grafos constituye una importante conexi\u00f3n entre diversos campos de la matem\u00e1tica, tales como la algoritmica, la geometria computacional y la teoria topol\u00f3gica de grafos. Dentro de ella, el estudio de las inmersiones ortogonales ocupan un lugar importante por su aplicaci\u00f3n a diversos problemas: dise\u00f1o de circuitos vlsi, donde da lugar a diversos problemas de optimizaci\u00f3n, creaci\u00f3n de diagramas de flujo y organigramas, dise\u00f1o de bases de datos en ingenieria del software y problemas de etiquetado de mapas y otras aplicaciones en sistemas de informaci\u00f3n geografica.  motivados por el trabajo de raghavan et al. Sobre el conocido problema eosp (emparejamiento ortogonal simple en el plano), nos planteamos en primer lugar la extensi\u00f3n de este problema a otras superficies. Este tema constituye la primera parte de la memoria que se presenta. Se estudian en ella la complejidad computacional de los problemas de emparejamiento ortogonal simple (eos), mostrando en primer lugar el comportamiento polinomial del problema cuando \u00fanicamente existen dos posibles caminos entre cada pareja de puntos. Sin embargo, el problema con un mayor numero de caminos entre cada pareja de puntos. Sin embargo, el problema con un mayor numero de caminos, asi como el problema general resultan ser np-completos y el problema de optimizaci\u00f3n asociado a este ultimo es por lo tanto np-duro.  otra ampliaci\u00f3n necesaria del problema eosp es estudiar, no las conexiones entre parejas, sino entre grupos de puntos usando inmersiones ortogonales de grafos, permitiendo un numero de codos superior a uno por cada inmersi\u00f3n. este estudio, realizado en el pleno ocupa la segunda parte de la memoria. en ella se clasifican los problemas de conexi\u00f3n ortogonal plana seg\u00fan su complejidad computacional. En primer lugar, caracterizamos una serie de problemas resolubles en tiempo polinomial mediante reducci\u00f3n a problemas de logica simbolica o<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Problemas de conexiones ortogonales<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Problemas de conexiones ortogonales <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Jos\u00e9 Ramon Portillo Fernandez <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Sevilla<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 14\/02\/2002<\/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>Mar\u00eda  De Los Angeles Garrido Vizuete<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: jose Mu\u00f1oz perez <\/li>\n<li>pedro Real jurado (vocal)<\/li>\n<li>ferran Hurtado d\u00edaz (vocal)<\/li>\n<li> Ramos alonso M\u00aa rosario (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Jos\u00e9 Ramon Portillo Fernandez El \u00e1rea de investigaci\u00f3n sobre dibujos de grafos constituye una importante conexi\u00f3n entre [&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":[1890,583,39247,13880,3747,3748,10816,126,10715],"tags":[49622,24726,49620,49621,41936,49623],"class_list":["post-15575","post","type-post","status-publish","format-standard","hentry","category-ciencia-de-los-ordenadores","category-geometria","category-geometria-afin","category-informatica","category-logica","category-logica-deductiva","category-logica-matematica","category-matematicas","category-sevilla","tag-ferran-hurtado-diaz","tag-jose-munoz-perez","tag-jose-ramon-portillo-fernandez","tag-maria-de-los-angeles-garrido-vizuete","tag-pedro-real-jurado","tag-ramos-alonso-ma-rosario"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/15575","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=15575"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/15575\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=15575"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=15575"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=15575"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}