enter search term and/or author name
Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
Jan Kynčl, Tomáš Vyskočil
Article No.: 8
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....
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
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...