Dynamic programming for graphs on surfaces

Inicio | ¿Qué es? | Contacto

English | Català

Consultar RECERCAT

Por comunidades y
colecciones Por fecha Por autores Por títulos Por temas (CDU)

Consultar departamento

Por fecha Por autores Por títulos Por temas (CDU)

Estadisticas

Del documento Todo RECERCAT

Mi RECERCAT

Entrar Alertas por correo-e

Directorio de otros repositorios

RECERCAT Principal > Universitat Politècnica de Catalunya > Documents de recerca > Visualizar documento

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/104306

dc.contributor	Universitat Politècnica de Catalunya. Departament de Matemàtiques
dc.contributor	Universitat Politècnica de Catalunya. MD - Matemàtica Discreta
dc.contributor.author	Rué Perna, Juan José
dc.contributor.author	Sau, Ignasi
dc.contributor.author	Thilikos, Dimitrios
dc.date	2010
dc.identifier.citation	Rue, J., Sau, I., Thilikos, D. Dynamic programming for graphs on surfaces. A: International Colloquium on Automata, Languages, and Programming. "Lecture notes in Computer Science (Volume 6198)". Bordeaux: Springer, 2010, p. 372-383.
dc.identifier.citation	978-3-642-14165-2
dc.identifier.citation	10.1007/978-3-642-14165-2_32
dc.identifier.uri	http://hdl.handle.net/2117/104306
dc.language.iso	eng
dc.publisher	Springer
dc.relation	info:eu-repo/grantAgreement/EC/FP7/208471/EU/Combinatorial methods, from enumerative topology to random discrete structures and compact data representations./EXPLOREMAPS
dc.rights	Attribution-NonCommercial-NoDerivs 3.0 Spain
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.subject	Àrees temàtiques de la UPC::Matemàtiques i estadística::Equacions diferencials i integrals
dc.subject	Dynamic programming
dc.subject	analysis of algorithms
dc.subject	parameterized algorithms
dc.subject	analytic combinatorics
dc.subject	graphs on surfaces
dc.subject	branch width dynamic programming
dc.subject	polyhedral embeddings
dc.subject	symbolic method
dc.subject	non-crossing partitions
dc.subject	Grafs, Teoria dels
dc.title	Dynamic programming for graphs on surfaces
dc.type	info:eu-repo/semantics/updatedVersion
dc.type	info:eu-repo/semantics/conferenceObject
dc.description.abstract	We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2O(k·log k). Our approach combines tools from topological graph theory and analytic combinatorics.

Mostrar el registro sencillo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Dynamic programming for graphs on surfaces

Rué Perna, Juan José; Sau, Ignasi; Thilikos, Dimitrios

Asymptotic enumeration of non-crossing partitions on surfaces

Rué Perna, Juan José; Sau, Ignasi; Thilikos Touloupas, Dimitrios

H-colorings of large degree graphs

Díaz Cort, Josep; Nesetril, Jaroslav; Serna Iglesias, María José; Thilikos, Dimitrios

On the number of labeled graphs of bounded treewidth

Baste, Julien; Noy Serrano, Marcos; Sau, Ignasi

Disecciones de un polígono en el plano proyectivo

Noy Serrano, Marcos; Rué Perna, Juan José

Accesibilidad | Aviso legal | Política de Cookies | Documentos de uso interno

Coordinación

Patrocinio