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.68214MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C20: Directed graphs (digraphs), tournaments
Related Items
Compressed Decision Problems in Hyperbolic Groups., Space-efficient algorithms for reachability in directed geometric graphs, Log-space algorithms for paths and matchings in \(k\)-trees, \textsc{ReachFewL} = \textsc{ReachUL}, On the power of unambiguity in log-space, Some Tractable Win-Lose Games