<link rel="stylesheet" href="styles.f3b1fba60ec7970c.css">

Publication:
Generating two-terminal directed acyclic graphs with a given complexity index by constraint logic programming

Loading...
Thumbnail Image

Departments

School / College / Institute

Program

KU-Authors

Organization Authors

Co-Authors

Drexl, Andreas

Kimms, Alf

Date

Language

Embargo Status

N/A

Journal Title

Journal ISSN

Volume Title

Alternative Title

Abstract

Two-terminal directed acyclic graphs (st-dags) are used to model problems in many areas and, hence, measures for their topology are needed. Complexity Index (CI) is one such measure and is defined as the minimum number of node reductions required to reduce a given st-dag into a single-arc graph, when used along with series and parallel reductions. In this research we present a constraint logic programming algorithm (implemented in ILOG's OPL-Optimization Programming Language) for the generation of st-dags with a given CI. To this end the complexity graph with a maximum matching of CI, the dominator tree, the reverse dominator tree and the st-dag are characterized by a set of constraints. Then a multi-phase algorithm is presented which searches the space described by the set of constraints. Finally, the computational performance of the algorithm is tested.

Source

Publisher

Elsevier Science Inc

Citation

item.page.haspartof

Source

Journal of Logic and Algebraic Programming

item.page.ispartofseries

item.page.edition

DOI

10.1016/S1567-8326(03)00057-2

item.page.datauri

item.page.link

Rights

N/A

Copyrights Note

Rights and licensing

N/A

Endorsement

Review

Supplemented By

Referenced By

Related Patent

Related Goal

Google Scholar
Scholar'da Ara ↗
Altmetric
Dimensions
PlumX Metrikleri
BIP! Indicators