Application of Hypergraphs to SMCs Selection

Abstract : 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.
Type de document :
Communication dans un congrès
Luis M. Camarinha-Matos; Nuno S. Barrento; Ricardo Mendonça. 5th Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS), Apr 2014, Costa de Caparica, Portugal. Springer, IFIP Advances in Information and Communication Technology, AICT-423, pp.249-256, 2014, Technological Innovation for Collective Awareness Systems. 〈10.1007/978-3-642-54734-8_28〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01274781
Contributeur : Hal Ifip <>
Soumis le : mardi 16 février 2016 - 11:20:19
Dernière modification le : jeudi 12 mai 2016 - 10:38:06
Document(s) archivé(s) le : samedi 12 novembre 2016 - 22:18:07

Fichier

978-3-642-54734-8_28_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Łukasz Stefanowicz, Marian Adamski, Remigiusz Wiśniewski, Jakub Lipiński. Application of Hypergraphs to SMCs Selection. Luis M. Camarinha-Matos; Nuno S. Barrento; Ricardo Mendonça. 5th Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS), Apr 2014, Costa de Caparica, Portugal. Springer, IFIP Advances in Information and Communication Technology, AICT-423, pp.249-256, 2014, Technological Innovation for Collective Awareness Systems. 〈10.1007/978-3-642-54734-8_28〉. 〈hal-01274781〉

Partager

Métriques

Consultations de la notice

28

Téléchargements de fichiers

30