A Method to Calculate Legal Sequence Number for Extended Series-Parallel Digraphs

概要

論文の詳細を見る
The problem of 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). We call a total ordering of the vertices as legal sequence and the problem as LSN(legal sequence number) problem. In this paper we study how to calculate LSN for a given directed acyclic graph G=(V, E). First we give the fundamental theorems for calculating LSN of general directed acyclic graphs. Then we give a way to calculate LSN for series-parallel digraphs and methods to transform a class of extended series-parallel digraphs into series-parallel ones. Finally we calculate LSN for the class of graphs, which are extended from series-parallel digraphs by adding so called bridge edges and bridge-path between specific paths.
一般社団法人情報処理学会の論文
1996-09-04