An algorithm for finding input-output constrained convex sets in an acyclic digraph

G. Gutin*, A. Johnstone, J. Reddington, E. Scott, A. Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

A set X of vertices of an acyclic graph is convex if any vertex on a directed walk between elements of X is itself in X. We construct an algorithm for generating all input-output constrained convex (IOCC) sets in an acyclic digraph, which uses several novel ideas. We show that the time complexity of our algorithm significantly improves the best one known from the literature. IOCC sets of acyclic digraphs are of interest in the area of modern embedded processor technology.

Original languageEnglish
JournalJournal of Discrete Algorithms
Volume13
Pages (from-to)47-58
ISSN1570-8667
DOIs
Publication statusPublished - 2012
Externally publishedYes

Keywords

  • Acyclic digraph
  • Algorithm
  • Convex set

Fingerprint

Dive into the research topics of 'An algorithm for finding input-output constrained convex sets in an acyclic digraph'. Together they form a unique fingerprint.

Cite this