The search functionality is under construction.

IEICE TRANSACTIONS on Fundamentals

A Computation Method of LSN for Extended 2-b-SPGs

Qi-Wei GE, Yasunori SUGIMOTO

  • Full Text Views

    0

  • Cite this

Summary :

Topological sorting is, given with a directed acyclic graph G=(V,E), to find a total ordering of the vertices such that if (u,v)E then u is ordered before v. Instead of topological sorting, we are interested in how many total orderings exist in a given directed acyclic graph. We call such a total ordering as legal sequence and the problem of finding total number of legal sequences as legal sequence number problem. In this paper, we firstly give necessary definitions and known results obtained in our previous research. Then we give a method how to obtain legal sequence number for a class of directed acyclic graphs, extended 2-b-SPGs. Finally we discuss the complexity of legal sequence number problem for extended 2-b-SPGs.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.11 pp.2838-2851
Publication Date
2001/11/01
Publicized
Online ISSN
DOI
Type of Manuscript
Special Section PAPER (Special Section on Concurrent Systems Technology)
Category

Authors

Keyword