Constructive linear time algorithms for branchwidth

Consultar RECERCAT

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

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Thilikos Touloupas, Dimitrios
dc.contributor.author	Bodlaender, Hans L.
dc.date	2000-10
dc.identifier.citation	Thilikos, D., Bodlaender, H. "Constructive linear time algorithms for branchwidth". 2000.
dc.identifier.uri	http://hdl.handle.net/2117/96447
dc.language.iso	eng
dc.relation	LSI-00-63-R
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica
dc.subject	Constructive linear time
dc.subject	Algorithms for branchwidth
dc.title	Constructive linear time algorithms for branchwidth
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.abstract	We prove that, for any fixed k, one can construct a linear time algorithm that checks if a graph has branchwidth at most k and, if so, outputs a branch decomposition of minimum width.

Thilikos Touloupas, Dimitrios; Serna Iglesias, María José; Bodlaender, Hans L.

Thilikos Touloupas, Dimitrios; Serna Iglesias, María José; Bodlaender, Hans L.

Díaz Cort, Josep; Kaminski, Marcin; Thilikos Touloupas, Dimitrios

Rué Perna, Juan José; Thilikos Touloupas, Dimitrios; Velona, Vasiliki

Stamatiou, Yannis; Thilikos Touloupas, Dimitrios

Coordinación

Patrocinio