Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming

Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this additional structure. On the negative side, we show wi...

ver descrição completa

Detalhes bibliográficos

Principais autores:	Li-Hsuan Chen, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil
Formato:	Artigo
Idioma:	Inglês
Publicado em:	MDPI AG 2018-07-01
Colecção:	Algorithms
Assuntos:	treewidth treedepth dynamic programming branching algorithm space lower bound
Acesso em linha:	http://www.mdpi.com/1999-4893/11/7/98
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!