BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Andrzej Lingas appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
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.
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.
A dominating set of a graph $G$ is a set $D\subseteq V_G$ such that every vertex in $V_G-D$ is adjacent to at least one vertex in $D$, and the domination number $γ(G)$ of $G$ is the minimum cardinality of a dominating set of $G$. A set $C\subseteq V_G$ is a covering set of $G$ if every edge of $G$ has at least one vertex in $C$. The covering number $β(G)$ of $G$ is the minimum cardinality of a covering set of $G$. The set of connected graphs $G$ for which $γ(G)=β(G)$ is denoted by ${\cal C}_{γ=β}$, while ${\cal B}$ denotes the set of all connected bipartite graphs in which the domination number is equal to the cardinality of the smaller partite set. In this paper, we provide alternative characterizations of graphs belonging to ${\cal C}_{γ=β}$ and ${\cal B}$. Next, we present a quadratic time algorithm for recognizing bipartite graphs belonging to ${\cal B}$, and, as a side result, we conclude that the algorithm of Arumugam et al. [2] allows to recognize all the graphs belonging to the set ${\cal C}_{γ=β}$ in quadratic time either. Finally, we consider the related problem of patrolling grids with mobile guards, and show that this problem can be solved in $O(n \log n + m)$ time, where $n$ is the number of line segments of the input grid and $m$ is the number of its intersection points.
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~$\mathcal{S}$ of vertices of a digraph $D$ and a positive integer $k$, the objective is to determine whether there is a subgraph $H=(\mathcal{V}_H,\mathcal{A}_H)$ of $D$ such that (a) $\mathcal{S} \subseteq \mathcal{V}_H$, (b) $H$ is the union of $k$ directed walks in $D$, and (c) the underlying graph of $H$ includes a Steiner tree for $\mathcal{S}$ in $D$. We provide several results on the polynomial time tractability, hardness, and parameterized complexity of the problem.
We study the problem of efficiently correcting an erroneous product of two $n\times n$ matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most $k$ erroneous entries running in $\tilde{O}(n^2+kn)$ time and a deterministic $\tilde{O}(kn^2)$-time algorithm for this problem (where the notation $\tilde{O}$ suppresses polylogarithmic terms in $n$ and $k$).
The number of triangulations of a planar n point set is known to be $c^n$, where the base $c$ lies between $2.43$ and $30.$ The fastest known algorithm for counting triangulations of a planar n point set runs in $O^*(2^n)$ time. The fastest known arbitrarily close approximation algorithm for the base of the number of triangulations of a planar n point set runs in time subexponential in $n.$ We present the first quasi-polynomial approximation scheme for the base of the number of triangulations of a planar point set.
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.
The exact complexity of geometric cuts and bisections is the longstanding open problem including even the dimension one. In this paper, we resolve this problem for dimension one (the real line) by designing an exact polynomial time algorithm. Our results depend on a new technique of dealing with metric equalities and their connection to dynamic programming. The method of our solution could be also of independent interest.
We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact complexity status of the optimal partition problems in one dimensional geometric metric settings. Our method of solution could be also of independent interest in other applications. We discuss also an extension of our method to the class of metrics induced by the bounded treewidth graphs.
We consider the problem of computing all-pairs shortest paths in a directed graph with real weights assigned to vertices. For an $n\times n$ 0-1 matrix $C,$ let $K_{C}$ be the complete weighted graph on the rows of $C$ where the weight of an edge between two rows is equal to their Hamming distance. Let $MWT(C)$ be the weight of a minimum weight spanning tree of $K_{C}.$ We show that the all-pairs shortest path problem for a directed graph $G$ on $n$ vertices with nonnegative real weights and adjacency matrix $A_G$ can be solved by a combinatorial randomized algorithm in time $$\widetilde{O}(n^{2}\sqrt {n + \min\{MWT(A_G), MWT(A_G^t)\}})$$ As a corollary, we conclude that the transitive closure of a directed graph $G$ can be computed by a combinatorial randomized algorithm in the aforementioned time. $\widetilde{O}(n^{2}\sqrt {n + \min\{MWT(A_G), MWT(A_G^t)\}})$ We also conclude that the all-pairs shortest path problem for uniform disk graphs, with nonnegative real vertex weights, induced by point sets of bounded density within a unit square can be solved in time $\widetilde{O}(n^{2.75})$.
Let G be an edge-weighted hypergraph on n vertices, m edges of size \le s, where the edges have real weights in an interval [1,W]. We show that if we can approximate a maximum weight matching in G within factor alpha in time T(n,m,W) then we can find a matching of weight at least (alpha-epsilon) times the maximum weight of a matching in G in time (epsilon^{-1})^{O(1)}max_{1\le q \le O(epsilon \frac {log {\frac n {epsilon}}} {log epsilon^{-1}})} max_{m_1+...m_q=m} sum_1^qT(min{n,sm_j},m_{j},(epsilon^{-1})^{O(epsilon^{-1})}). In particular, if we combine our result with the recent (1-ε)-approximation algorithm for maximum weight matching in graphs due to Duan and Pettie whose time complexity has a poly-logarithmic dependence on W then we obtain a (1-ε)-approximation algorithm for maximum weight matching in graphs running in time (epsilon^{-1})^{O(1)}(m+n).
In this paper, we establish two necessary conditions for a joint triangulation of two sets of $n$ points in the plane and conjecture that they are sufficient. We show that these necessary conditions can be tested in $O(n^3)$ time. For the problem of a joint triangulation of two simple polygons of $n$ vertices, we propose an $O(n^3)$ time algorithm for constructing a joint triangulation using dynamic programming.