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   Vol.E84-A   No.11   pp.2838-2851
Publication Date: 2001/11/01
Online ISSN: 
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)>>
Buy this Article

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.