Graphs (networks) are an important tool to model data in different domains.
Real-world graphs are usually directed, where the edges have a direction and
they are not symmetric. Betweenness centrality is an important index widely
used to analyze networks. In this paper, first given a directed network $G$ and
a vertex $r \in V(G)$, we propose an exact algorithm to compute betweenness
score of $r$. Our algorithm pre-computes a set $\mathcal{RV}(r)$, which is used
to prune a huge amount of computations that do not contribute to the
betweenness score of $r$. Time complexity of our algorithm depends on
$|\mathcal{RV}(r)|$ and it is respectively
$\Theta(|\mathcal{RV}(r)|\cdot|E(G)|)$ and
$\Theta(|\mathcal{RV}(r)|\cdot|E(G)|+|\mathcal{RV}(r)|\cdot|V(G)|\log |V(G)|)$
for unweighted graphs and weighted graphs with positive weights.
$|\mathcal{RV}(r)|$ is bounded from above by $|V(G)|-1$ and in most cases, it
is a small constant. Then, for the cases where $\mathcal{RV}(r)$ is large, we
present a simple randomized algorithm that samples from $\mathcal{RV}(r)$ and
performs computations for only the sampled elements. We show that this
algorithm provides an $(\epsilon,\delta)$-approximation to the betweenness
score of $r$. Finally, we perform extensive experiments over several real-world
datasets from different domains for several randomly chosen vertices as well as
for the vertices with the highest betweenness scores. Our experiments reveal
that for estimating betweenness score of a […]
Membrane computing is a branch of natural computingwhich abstracts fromthe
structure and the functioning of living cells. The computation models obtained
in the field of membrane computing are usually called P systems. P systems have
been used to solve computationally hard problems efficiently on the assumption
that the execution of each rule is completed in exactly one time-unit (a global
clock is assumed for timing and synchronizing the execution of rules). However,
in biological reality, different biological processes take different times to
be completed, which can also be influenced by many environmental factors. In
this work, with this biological reality, we give a time-free solution to
independent set problemusing P systems with active membranes, which solve the
problem independent of the execution time of the involved rules.
We first design an $\mathcal{O}(n^2)$ solution for finding a maximum induced
matching in permutation graphs given their permutation models, based on a
dynamic programming algorithm with the aid of the sweep line technique. With
the support of the disjoint-set data structure, we improve the complexity to
$\mathcal{O}(m + n)$. Consequently, we extend this result to give an
$\mathcal{O}(m + n)$ algorithm for the same problem in trapezoid graphs. By
combining our algorithms with the current best graph identification algorithms,
we can solve the MIM problem in permutation and trapezoid graphs in linear and
$\mathcal{O}(n^2)$ time, respectively. Our results are far better than the best
known $\mathcal{O}(mn)$ algorithm for the maximum induced matching problem in
both graph classes, which was proposed by Habib et al.
A zero forcing set is a set $S$ of vertices of a graph $G$, called forced
vertices of $G$, which are able to force the entire graph by applying the
following process iteratively: At any particular instance of time, if any
forced vertex has a unique unforced neighbor, it forces that neighbor. In this
paper, we introduce a variant of zero forcing set that induces independent
edges and name it as edge-forcing set. The minimum cardinality of an
edge-forcing set is called the edge-forcing number. We prove that the
edge-forcing problem of determining the edge-forcing number is NP-complete.
Further, we study the edge-forcing number of butterfly networks. We obtain a
lower bound on the edge-forcing number of butterfly networks and prove that
this bound is tight for butterfly networks of dimensions 2, 3, 4 and 5 and
obtain an upper bound for the higher dimensions.
We study the query version of constrained minimum link paths between two
points inside a simple polygon $P$ with $n$ vertices such that there is at
least one point on the path, visible from a query point. The method is based on
partitioning $P$ into a number of faces of equal link distance from a point,
called a link-based shortest path map (SPM). Initially, we solve this problem
for two given points $s$, $t$ and a query point $q$. Then, the proposed
solution is extended to a general case for three arbitrary query points $s$,
$t$ and $q$. In the former, we propose an algorithm with $O(n)$ preprocessing
time. Extending this approach for the latter case, we develop an algorithm with
$O(n^3)$ preprocessing time. The link distance of a $q$-$visible$ path between
$s$, $t$ as well as the path are provided in time $O(\log n)$ and $O(m+\log
n)$, respectively, for the above two cases, where $m$ is the number of links.