For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Computation Method of LSN for Extended 2-b-SPGs
Qi-Wei GE Yasunori SUGIMOTO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2001/11/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Concurrent Systems Technology)
topological sorting, directed acyclic graph, series-parallel graph, legal sequence, legal sequence number,
Full Text: PDF(1.5MB)>>
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.