Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
From MaRDI portal
Publication:3183622
DOI10.1007/978-3-642-03409-1_29zbMath1252.68214OpenAlexW2163153241MaRDI QIDQ3183622
Fabian Wagner, Thomas Thierauf
Publication date: 20 October 2009
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03409-1_29
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)
Related Items (6)
Log-space algorithms for paths and matchings in \(k\)-trees ⋮ On the power of unambiguity in log-space ⋮ Space-efficient algorithms for reachability in directed geometric graphs ⋮ Some Tractable Win-Lose Games ⋮ \textsc{ReachFewL} = \textsc{ReachUL} ⋮ Compressed Decision Problems in Hyperbolic Groups.
This page was built for publication: Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
