1 citations · 1 across the 3 of their papers we have counts for
4 papers
The blue pebbling cost and the space in tree-like and negative Resolution
Lisa-Marie Jaser, Jacobo Torán
The red-blue pebble game is a well known two-player game on graphs that has been used in the past as a tool to analyze complexity measures in several computation models as well as…
Pebble Games and Algebraic Proof Systems
Lisa-Marie Jaser, Jacobo Toran
Analyzing refutations of the well known 0pebbling formulas Peb we prove some new strong connections between pebble games and algebraic proof system, showing that there is a pa…
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
V. Arvind, Johannes Köbler, Sebastian Kuhnert +1
Lubiw showed that several variants of Graph Isomorphism are NP-complete, where the solutions are required to satisfy certain additional constraints [SICOMP 10, 1981]. One of these,…
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs
Bireswar Das, Jacobo Toran, Fabian Wagner
The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time [Bod90],[YBFT99]. We give restric…