Gabriel Semanišin

(P.J. Šafárik University Košice, Slovakia)

On two problems related to communication in wireless sensor networks

We discuss two problems that arises in connection with study of communication protocols in wireless sensor networks. The first one provides a generalisation of Matching Finding Problem and the second one provides a generalisation of Vertex Cover Problem and leads to a new graph theoretical invariant.

Problem 1:
Given a positive integer d and a bipartite graph $G = (U \cup V, E)$ with n vertices and m edges. A bounded-degree semi-matching on $G$ is a set of edges $M \subseteq E$ such that each vertex in $U$ is incident to exactly one edge in $M$ and every vertex from $V$ is incident to at most d edges of $G$. We discuss a few approaches for solving this problem and provide an algorithm with $O(\sqrt{n} m)$ running time.

Problem 2:
Let $G$ be a graph and $k\ge 2$ an arbitrary, fixed integer. Then $S\subset V(G)$ is the k-path security set of $G$ if every path on k vertices in $G$ contains a vertex from $S$. The k-path security number $\psi_k(G)$ of $G$ is the cardinality of a minimum k-path security set in $G$. We present some exact values and estimations of this parameter and provide algorithms for special classes of graphs.

Serdecznie zapraszamy wszystkich chêtnych !