Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 1 Issue 3, March 2010

Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
Jan Kynčl, Tomáš Vyskočil
Article No.: 8
DOI: 10.1145/1714450.1714451

Directed reachability (or briefly reachability) is the following decision problem: given a directed graph G and two of its vertices s,t, determine whether there is a directed path from s to t in G....

Formula Caching in DPLL
Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind
Article No.: 9
DOI: 10.1145/1714450.1714452

We consider extensions of the DPLL approach to satisfiability testing that add a version of memoization, in which formulas that the algorithm has previously shown to be unsatisfiable are remembered for later use. Such formula caching...

Planarity, Determinants, Permanents, and (Unique) Matchings
Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan
Article No.: 10
DOI: 10.1145/1714450.1714453

Viewing the computation of the determinant and the permanent of integer matrices as combinatorial problems on associated graphs, we explore the restrictiveness of planarity on their complexities and show that both problems remain as hard as in the...