The search functionality is under construction.

IEICE TRANSACTIONS on Fundamentals

On an Algorithm to Detect Positive Cycles in a Constraint Graph for Layout Compaction

Kunihiko ISHIMA, Shuji TSUKIYAMA

  • Full Text Views

    0

  • Cite this

Summary :

In this letter, we consider the following problem: Given a weighted digraph G=[V, EaEb] such that subgraph Ga=[V, Ea] of G is an acyclic graph with a single source vertex and the weight of each edge in Eb is negative, if G has a positive cycle, then locate them as many as possible; otherwise, compute the longest path length from source vertex to each vertex of V. Then, we propose an algorithm to this problem and show some experimental results to demonstrate the efficiency of the proposed algorithm.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E74-A No.11 pp.3613-3616
Publication Date
1991/11/25
Publicized
Online ISSN
DOI
Type of Manuscript
LETTER
Category
Algorithms, Data Structures and Computational Complexity

Authors

Keyword