Application of Hypergraphs to SMCs Selection - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

Application of Hypergraphs to SMCs Selection

Łukasz Stefanowicz
  • Fonction : Auteur
  • PersonId : 976773
Marian Adamski
  • Fonction : Auteur
  • PersonId : 976774
Remigiusz Wiśniewski
  • Fonction : Auteur
  • PersonId : 976775
Jakub Lipiński
  • Fonction : Auteur
  • PersonId : 976776

Résumé

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.
Fichier principal
Vignette du fichier
978-3-642-54734-8_28_Chapter.pdf (4 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01274781 , version 1 (16-02-2016)

Licence

Paternité

Identifiants

Citer

Łukasz Stefanowicz, Marian Adamski, Remigiusz Wiśniewski, Jakub Lipiński. Application of Hypergraphs to SMCs Selection. 5th Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS), Apr 2014, Costa de Caparica, Portugal. pp.249-256, ⟨10.1007/978-3-642-54734-8_28⟩. ⟨hal-01274781⟩
41 Consultations
121 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More