Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 9 Issue 4, January 2018

Parameterized Testability
Kazuo Iwama, Yuichi Yoshida
Article No.: 16
DOI: 10.1145/3155294

Parameterized Property Testing of Functions
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
Article No.: 17
DOI: 10.1145/3155296

On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs
Michał Pilipczuk, Marcin Wrochna
Article No.: 18
DOI: 10.1145/3154856

An O(nε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
Diptarka Chakraborty, Raghunath Tewari
Article No.: 19
DOI: 10.1145/3154857

Given a graph G and two vertices s and t in it, graph reachability is the problem of checking whether there exists a path from s to t in G. We show that reachability in directed layered planar...

Metric 1-Median Selection: Query Complexity vs. Approximation Ratio
Ching-Lueh Chang
Article No.: 20
DOI: 10.1145/3154858