Dynamic programming for graphs on surfaces

Inici | Què és? | Contacte

English | Castellano

Consultar RECERCAT

Per comunitats i
col·leccions Per data Per autors Per títols Per matèries

Consultar col·lecció

Per data Per autors Per títols Per matèries

Estadístiques

Del document Tot RECERCAT

El meu RECERCAT

Entrar Alertes per correu-e

Directori d’altres repositoris

Pàgina inicial del RECERCAT > Universitat Politècnica de Catalunya > Documents de recerca > Visualitza document

Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: 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.

Mostra el registre simple del document

Documents relacionats

Altres documents del mateix 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é

Accessibilitat | Avís legal | Política de Cookies | Documents d'ús intern

Coordinació

Patrocini