A Computation Method of LSN for Extended 2-b-SPGs(Special Section on Concurrent Systems Technology)
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 一般社団法人電子情報通信学会の論文
- 2001-11-01
著者
関連論文
- Performance Evaluation on Transient Time of Dynamic Workflow Changes(Special Section on Concurrent Systems Technology)
- Performance Evaluation on Change Time of Dynamic Workflow Changes (Special Section on Concurrent Systems Technology)
- A Petri Net Based Public-Key Cryptography:PNPKC(Special Section on Papers Selected from ITC-CSCC 2000)
- Two-Processor Scheduling of General Acyclic SWITCH-less Program Nets via Hybrid Priority Lists (Special Section of Selected Papers from the 12th Workshop on Circuit and Systems in Karuizawa)
- A New Proposal to Two-Processor Scheduling Problem for SWITCH-less Program Nets(Concurrent Systems)(Concurrent Systems and Hybrid Systems)
- Computation of Minimum Firing Time for General Self-Cleaning SWITCH-Less Program Nets(Special Section of Papers Selected from ITC-CSCC'97)
- A Computation Method of LSN for Extended 2-b-SPGs(Special Section on Concurrent Systems Technology)
- Incorporation of Cycles and Inhibitory Arcs into the Timed Petri Net Model of Signaling Pathway