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

Li Hsuan Chen; Felix Reidl; Peter Rossmanith; Fernando Sánchez Villaamil

doi:10.3390/a11070098

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

Li Hsuan Chen, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil

Department of Computer Science

Research output: Contribution to journal › Article › peer-review

Original language	English
Article number	98
Pages (from-to)	1-17
Number of pages	17
Journal	Algorithms
Volume	11
Issue number	7
DOIs	https://doi.org/10.3390/a11070098
Publication status	Published - 1 Jul 2018

Keywords

Branching algorithm
Dynamic programming
Space lower bound
Treedepth
Treewidth

Access to Document

10.3390/a11070098Licence: CC BY

Cite this

@article{5c58a2a15f734285bfb0a91ee68a1a56,

title = "Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming",

keywords = "Branching algorithm, Dynamic programming, Space lower bound, Treedepth, Treewidth",

author = "Chen, {Li Hsuan} and Felix Reidl and Peter Rossmanith and Villaamil, {Fernando S{\'a}nchez}",

year = "2018",

month = jul,

day = "1",

doi = "10.3390/a11070098",

language = "English",

volume = "11",

pages = "1--17",

journal = "Algorithms",

issn = "1999-4893",

publisher = "Multidisciplinary Digital Publishing Institute (MDPI)",

number = "7",

}

TY - JOUR

T1 - Width, Depth, and Space

T2 - Tradeoffs between Branching and Dynamic Programming

AU - Chen, Li Hsuan

AU - Reidl, Felix

AU - Rossmanith, Peter

AU - Villaamil, Fernando Sánchez

PY - 2018/7/1

Y1 - 2018/7/1

KW - Branching algorithm

KW - Dynamic programming

KW - Space lower bound

KW - Treedepth

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85050255824&partnerID=8YFLogxK

U2 - 10.3390/a11070098

DO - 10.3390/a11070098

M3 - Article

AN - SCOPUS:85050255824

SN - 1999-4893

VL - 11

SP - 1

EP - 17

JO - Algorithms

JF - Algorithms

IS - 7

M1 - 98

ER -

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

Keywords

Access to Document

Other files and links

Cite this