Application of Hypergraphs to SMCs Selection

Autor:	Jakub Lipiński, Łukasz Stefanowicz, Remigiusz Wiśniewski, Marian Adamski
Rok vydání:	2014
Předmět:	Hypergraph Polynomial Theoretical computer science Backtracking Computer science TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Concurrency Transversal (combinatorics) Petri net Time complexity Selection (genetic algorithm) MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj:	Technological Innovation for Collective Awareness Systems ISBN: 9783642547331 DoCEIS
DOI:	10.1007/978-3-642-54734-8_28
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::114949c165b300748de4a2fee2701e61 https://doi.org/10.1007/978-3-642-54734-8_28 Zobrazit plný text záznamu