The search functionality is under construction.

The search functionality is under construction.

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-SPG*s. Finally we discuss the complexity of legal sequence number problem for extended *2-b-SPG*s.

- 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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

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-SPG*s. Finally we discuss the complexity of legal sequence number problem for extended *2-b-SPG*s.

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-SPG*s. Finally we discuss the complexity of legal sequence number problem for extended *2-b-SPG*s.

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-SPG*s. Finally we discuss the complexity of legal sequence number problem for extended *2-b-SPG*s.

ER -