BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Andrzej Lingas contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph 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.
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.