Dynamic programming for graphs on surfaces

Home | About RECERCAT | Contact

Català | Castellano

All of RECERCAT

By Communities &
Collections By Defense Date By Authors By Titles By Subject

This Collection

By Defense Date By Authors By Titles By Subject

Statistics

View Statistics All RECERCAT

My RECERCAT

Other repositories directory

RECERCAT Home > Universitat Politècnica de Catalunya > Documents de recerca > View document

To access the full text documents, please follow this link: 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.

Show simple item record

All of RECERCAT

This Collection

Statistics

My RECERCAT

Related documents

Other documents of the same author