Algorithms for Generating Convex Sets in Acyclic Digraphs

Computer Science – Discrete Mathematics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

A set $X$ of vertices of an acyclic digraph $D$ is convex if $X\neq \emptyset$ and there is no directed path between vertices of $X$ which contains a vertex not in $X$. A set $X$ is connected if $X\neq \emptyset$ and the underlying undirected graph of the subgraph of $D$ induced by $X$ is connected. Connected convex sets and convex sets of acyclic digraphs are of interest in the area of modern embedded processor technology. We construct an algorithm $\cal A$ for enumeration of all connected convex sets of an acyclic digraph $D$ of order $n$. The time complexity of $\cal A$ is $O(n\cdot cc(D))$, where $cc(D)$ is the number of connected convex sets in $D$. We also give an optimal algorithm for enumeration of all (not just connected) convex sets of an acyclic digraph $D$ of order $n$. In computational experiments we demonstrate that our algorithms outperform the best algorithms in the literature. Using the same approach as for $\cal A$, we design an algorithm for generating all connected sets of a connected undirected graph $G$. The complexity of the algorithm is $O(n\cdot c(G)),$ where $n$ is the order of $G$ and $c(G)$ is the number of connected sets of $G.$ The previously reported algorithm for connected set enumeration is of running time $O(mn\cdot c(G))$, where $m$ is the number of edges in $G.$

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Algorithms for Generating Convex Sets in Acyclic Digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithms for Generating Convex Sets in Acyclic Digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for Generating Convex Sets in Acyclic Digraphs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-115963

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.