Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)

DOI10.1007/978-3-319-67089-8_13zbMath1478.68106OpenAlexW2748423797MaRDI QIDQ1685795

Tomoyuki Yamakami

Publication date: 20 December 2017

Full work available at URL: https://doi.org/10.1007/978-3-319-67089-8_13

zbMATH Keywords

directed s-t connectivityhypo-linear spacelinear-space hypothesisNL optimizationNL searchshort reductionsub-linear space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

The 2CNF Boolean formula satisfiability problem and the linear space hypothesis ⋮ State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice

This page was built for publication: Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)