2026-05-13T06:50:20Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00130170 2025-01-21T00:15:01Z 6504:8117:8119

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. conference paper 情報処理学会 1996-09-04 application/pdf 全国大会講演論文集 ソフトウェア科学・工学 第53回 157 158 AN00349328 https://ipsj.ixsq.nii.ac.jp/record/130170/files/KJ00001341925.pdf eng