BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We study the problem of determining the Boolean product of two n\times n Boolean matrices in an unconventional computational model allowing for mechanical operations. We show that O(n^2) operations are sufficient to compute the product in this model.
We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset~S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(VH,AH) of D such that (a) S⊆VH, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for S in D. We provide several results on the polynomial time tractability, hardness, and parameterized complexity of the problem.
We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multi-variate polynomials over a finite field of characteristic two for non-identity with zero. In effect, we show that a minimum-cost flow of value k in a network with n vertices, a sink and a source, integral edge capacities and positive integral edge costs polynomially bounded in n can be found by a randomized PRAM, with errors of exponentially small probability in n, running in O(k\log (kn)+\log^2 (kn)) time and using 2^{k}(kn)^{O(1)} processors. Thus, in particular, for the minimum-cost flow of value O(\log n), we obtain an RNC^2 algorithm.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.