Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree | Zendy

Fedor V. Fomin | Zendy; Petteri Kaski | Zendy; Daniel Lokshtanov | Zendy; Fahad Panolan | Zendy; Saket Saurabh | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree

Author(s) -

Fedor V. Fomin,

Petteri Kaski,

Daniel Lokshtanov,

Fahad Panolan,

Saket Saurabh

Publication year - 2019

Publication title -

siam journal on discrete mathematics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.843

H-Index - 66

eISSN - 1095-7146

pISSN - 0895-4801

DOI - 10.1137/17m1140030

Subject(s) - parameterized complexity , mathematics , steiner tree problem , combinatorics , pspace , exponential function , discrete mathematics , tree (set theory) , time complexity , polynomial , space (punctuation) , algorithm , computational complexity theory , computer science , mathematical analysis , operating system

In the Steiner Tree problem, we are given as input a connected $n$-vertex graph with edge weights in $\{1,2,\ldots,W\}$, and a set of $k$ terminal vertices. Our task is to compute a minimum-weight ...

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research