%0 Conference Proceedings
%T Application of Hypergraphs to SMCs Selection
%+ University of Zielona Góra
%A Stefanowicz, Łukasz
%A Adamski, Marian
%A Wiśniewski, Remigiusz
%A Lipiński, Jakub
%Z Part 9: Petri Nets
%< avec comité de lecture
%( IFIP Advances in Information and Communication Technology
%B 5th Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS)
%C Costa de Caparica, Portugal
%Y Luis M. Camarinha-Matos
%Y Nuno S. Barrento
%Y Ricardo Mendonça
%I Springer
%3 Technological Innovation for Collective Awareness Systems
%V AICT-423
%P 249-256
%8 2014-04-07
%D 2014
%R 10.1007/978-3-642-54734-8_28
%K Petri net
%K State Machine Component (SMC)
%K hypergraph
%K exact transversal
%K concurrency hypergraph
%K sequential hypergraph
%K backtracking
%K greedy
%K algorithm of exact transversals
%Z Computer Science [cs]Conference papers
%X The paper deals with selection of State Machine Components (SMCs) based on Hypergraphs theory. The entire selection process use Petri nets as benchmarks. As it is known, Petri nets are used for modeling of concurrency processes. The SMCs selection problem is classified as NP-Hard which means there does not exist polynomial algorithm which provides an exact solution. In the article we show three SMCs selection methods, advantages and disadvantages of each, results of comparison between traditional methods (exponential backtracking, polynomial greedy) and an exact transversal method based on hypergraphs theory, their efficiency and propriety. An exact transversal method allows to obtain exact solution in polynomial time if selection hypergraph belongs to xt-hypergraph class.
%G English
%Z TC 5
%Z WG 5.5
%2 https://inria.hal.science/hal-01274781/document
%2 https://inria.hal.science/hal-01274781/file/978-3-642-54734-8_28_Chapter.pdf
%L hal-01274781
%U https://inria.hal.science/hal-01274781
%~ IFIP
%~ IFIP-AICT
%~ IFIP-TC
%~ IFIP-TC5
%~ IFIP-AICT-423
%~ IFIP-WG
%~ IFIP-WG5-5