**An algorithm for finding connected convex subgraphs of an acyclic digraph.** / Gutin, G.; Johnstone, A.; Reddington, Joseph; Scott, E.; Soleimanfallah, A.; Yeo, Anders.

Research output: Contribution to conference › Paper › peer-review

Published

A subgraph H of an acyclic digraph D is convex if there is no directed path between vertices of H which contains an arc not in H. A digraph D is connected if the underlying undirected graph of D is connected. We construct an algorithm for enumeration of all connected convex subgraphs of a connected acyclic digraph D of order n. The time complexity of the algorithm is O(n · cc(D)), where cc(D) is the number of connected convex subgraphs in D. The space complexity is O(n 2). Connected convex subgraphs of connected acyclic digraphs are of interest in the area of modern embedded processors technology. Our computational experiments demonstrate that our algorithm is better than the state-of-the-art algorithm of Chen, Maskell and Sun. Moreover, unlike the algorithm of Chen, Maskell and Sun, our algorithm has a provable (almost) optimal worst time complexity. Using the same approach, we design an algorithm for generating all connected induced subgraphs of a connected undirected graph G. The complexity of the algorithm is O(n · c(G)), where n is the order of G and c(G) is the number of connected induced subgraphs of G. The previously reported algorithm for connected induced subgraph enumeration is of running time O(mn · c(G)), where m is the number of edges in G.

Original language | English |
---|---|

Pages | 69-82 |

Number of pages | 14 |

DOIs | |

Publication status | Published - 2007 |

## An Algorithm for Finding Input-Output Constrained Convex Sets in an Acyclic Digraph

Research output: Contribution to journal › Article › peer-review

## Algorithms for generating convex sets in acyclic digraphs

Research output: Contribution to journal › Article › peer-review

This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 1796718