Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace:

Dynamic programming for graphs on surfaces
Rué Perna, Juan José; Sau, Ignasi; Thilikos, Dimitrios
Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. MD - Matemàtica Discreta
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.
Àrees temàtiques de la UPC::Matemàtiques i estadística::Equacions diferencials i integrals
Dynamic programming
analysis of algorithms
parameterized algorithms
analytic combinatorics
graphs on surfaces
branch width dynamic programming
polyhedral embeddings
symbolic method
non-crossing partitions
Grafs, Teoria dels
Attribution-NonCommercial-NoDerivs 3.0 Spain

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Rué Perna, Juan José; Sau, Ignasi; Thilikos, Dimitrios
Rué Perna, Juan José; Sau, Ignasi; Thilikos Touloupas, Dimitrios
Díaz Cort, Josep; Nesetril, Jaroslav; Serna Iglesias, María José; Thilikos, Dimitrios