A Method of Finding Legal Sequence Number for a Class of Extended Series-Parallel Digraphs (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 一般社団法人電子情報通信学会の論文
- 1997-04-25
著者
-
Ge Qi-wei
Faculty Of Education Yamaguchi University
-
Yoshioka Naomi
Faculty Of Education Yamaguchi University
関連論文
- An Optimal Two-Processor Scheduling for a Class of Program Nets via a Hybrid Priority List (特集 並列処理)
- A Flexible and Efficient Workflow Change Type : Selective Shift(Papers Selected from ITC-CSCC 2004)
- Modeling and Performance Evaluation on Change Time for Migrate Dynamic Workflow Changes(Special Section on Papers Selected from ITC-CSCC 2002)
- WF-Net Based Modeling and Soundness Verification of Interworkflows(Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
- Complexity and a Heuristic Algorithm of Computing Parallel Degree for Program Nets with SWITCH-Nodes(Concurrent Systems,Concurrent/Hybrid Systems: Theory and Applications)
- Performance Evaluation on Worst Change Time of Flush and SCO Dynamic Changes for State Machine WF-Nets(Papers Selected from 2005 International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC 2005))
- Dead Problem of Program Nets(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
- Computation Methods of Maximum Throughput for MG/SMWF-Nets with Conflict-Free Resources(Concurrent Systems)(Concurrent Systems and Hybrid Systems)
- Parallel Degree of Well-Structured Workflow Nets
- Delay Time Determination for the Timed Petri Net Model of a Signaling Pathway Based on Its Structural Information
- On Verification of Token Self-Cleanness of Data-Flow Program Nets (Special Section of Papers Selected from JTC-CSCC'95)
- Performance Evaluation of a Two-Processor Scheduling Method for Acyclic SWITCH-less Program Nets(Papers Selected from ITC-CSCC 2004)
- An Optimal Two-Processor Scheduling for a Class of SWITCH-less Program Nets with Combined OR-nodes(Special Section on Papers Selected from ITC-CSCC 2001)
- A Two-Processor Scheduling Method for a Class of Program Nets with Unity Node Firing Time (Special Section on Concurrent Systems Technology)
- A Method of Finding Legal Sequence Number for a Class of Extended Series-Parallel Digraphs (Special Section on Discrete Mathematics and Its Applications)
- An Effective Dynamic Priority List for 2-Processor Scheduling of Program Nets(Special Section of Selected Papers from the 13th Workshop on Circuits and Systems in Karuizawa)
- Incorporation of Cycles and Inhibitory Arcs into the Timed Petri Net Model of Signaling Pathway