A Computation Method of <I>LSN</I> for Extended <I>2-b-SPG</I>s

Qi-Wei GE; Yasunori SUGIMOTO

A Computation Method of LSN for Extended 2-b-SPGs

Qi-Wei GE, Yasunori SUGIMOTO

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 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.11 pp.2838-2851

Publication Date: 2001/11/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Concurrent Systems Technology)

Category

Cite this

Copy

Qi-Wei GE, Yasunori SUGIMOTO, "A Computation Method of LSN for Extended 2-b-SPGs" in IEICE TRANSACTIONS on Fundamentals, vol. E84-A, no. 11, pp. 2838-2851, November 2001, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_11_2838/_p

Copy

@ARTICLE{e84-a_11_2838,
author={Qi-Wei GE, Yasunori SUGIMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Computation Method of LSN for Extended 2-b-SPGs},
year={2001},
volume={E84-A},
number={11},
pages={2838-2851},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - A Computation Method of LSN for Extended 2-b-SPGs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2838
EP - 2851
AU - Qi-Wei GE
AU - Yasunori SUGIMOTO
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2001
AB - 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.
ER -