Time Complexity Analysis of the Minimal Siphon Extraction Problem of Petri Nets

Masahiro YAMAUCHI; Toshimasa WATANABE

Copy

Masahiro YAMAUCHI, Toshimasa WATANABE, "Time Complexity Analysis of the Minimal Siphon Extraction Problem of Petri Nets" in IEICE TRANSACTIONS on Fundamentals, vol. E82-A, no. 11, pp. 2558-2565, November 1999, doi: .
Abstract: Given a Petri net N=(P, T, E), a siphon is a set S of places such that the set of input transitions to S is included in the set of output transitions from S. Concerning extraction of one or more minimal siphons containing a given specified set Q of places, the paper shows several results on polynomial time solvability and NP-completeness, mainly for the case |Q| 1.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_11_2558/_p

Copy

@ARTICLE{e82-a_11_2558,
author={Masahiro YAMAUCHI, Toshimasa WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Time Complexity Analysis of the Minimal Siphon Extraction Problem of Petri Nets},
year={1999},
volume={E82-A},
number={11},
pages={2558-2565},
abstract={Given a Petri net N=(P, T, E), a siphon is a set S of places such that the set of input transitions to S is included in the set of output transitions from S. Concerning extraction of one or more minimal siphons containing a given specified set Q of places, the paper shows several results on polynomial time solvability and NP-completeness, mainly for the case |Q| 1.},
keywords={},
doi={},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - Time Complexity Analysis of the Minimal Siphon Extraction Problem of Petri Nets
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2558
EP - 2565
AU - Masahiro YAMAUCHI
AU - Toshimasa WATANABE
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 1999
AB - Given a Petri net N=(P, T, E), a siphon is a set S of places such that the set of input transitions to S is included in the set of output transitions from S. Concerning extraction of one or more minimal siphons containing a given specified set Q of places, the paper shows several results on polynomial time solvability and NP-completeness, mainly for the case |Q| 1.
ER -