The search functionality is under construction.

IEICE TRANSACTIONS on Fundamentals

A Method of Finding Legal Sequence Number for a Class of Extended Series-Parallel Digraphs

Qi-Wei GE, Naomi YOSHIOKA

  • 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 finding total orderings, we wish to find out how many total orderings exist in a given directed acyclic graph G = (V, E). Here we call a total ordering as legal sequence and the problem as legal sequence number problem. In this paper, we first propose theorems on equivalent transformation of graphs with respect to legal sequence number. Then we give a formula to calculate legal sequence number of basic series-parallel digraphs and a way of the calculation for general series-parallel digraphs. Finally we apply our results to show how to obtain legal sequence number for a class of extended series-parallel digraphs.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.4 pp.635-642
Publication Date
1997/04/25
Publicized
Online ISSN
DOI
Type of Manuscript
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category

Authors

Keyword