Algorithms for generating convex sets in acyclic digraphs
| Autor: | Arezou Soleimanfallah, Paul Balister, Stefanie Gerke, Joseph Reddington, Elizabeth Scott, Adrian Johnstone, Anders Yeo, Gregory Gutin |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
FOS: Computer and information sciences
Convex hull Embedded processors Discrete Mathematics (cs.DM) Convex set Proper convex function Subderivative Convex sets Theoretical Computer Science Combinatorics Acyclic digraphs Computer Science::Discrete Mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Computer Science - Data Structures and Algorithms Convex polytope Discrete Mathematics and Combinatorics Data Structures and Algorithms (cs.DS) Convex combination Enumeration algorithms Orthogonal convex hull Mathematics Convex analysis Discrete mathematics Mathematics::Combinatorics Computational Theory and Mathematics Algorithm Computer Science - Discrete Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Journal of Discrete Algorithms. 7:509-518 |
| ISSN: | 1570-8667 |
| DOI: | 10.1016/j.jda.2008.07.008 |
| Popis: | 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.$ |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect