Search

Pri posedanju učencev v šolske klopi, organizaciji tekmovanj iz znanja, organizaciji poroke in pri drugih podobnih dogodkih se srečamo s problemom razmestitve. Gre za enega od tistih problemov, ki so na začetku videti trivialni, saj so pravila posedanja po navadi preprosta in razumljiva. Zaradi tega se organizatorji zgoraj navedenih dogodkov velikokrat odločijo za izdelavo sedežnega reda na roke, kar hitro postane eno najbolj zamudnih del organizatorja. V okviru diplomske naloge je bil problem razmestitve natančno opredeljen, dokazano je bilo, da je problem NP-poln in izdelana je bila spletna aplikacija za samodejno izdelavo sedežnih redov. Poleg samodejne izdelave sedežnega reda aplikacija ponuja tudi uporabniške vmesnike za vnos podatkov o osebah, izdelavo topologije sedežnih mest in prikaz končne razmestitve. We encounter the arrangement problem while making classroom seating plans, organizing knowledge competitions, organizing weddings and other similar events. This is one of those problems that seem trivial at first, because the rules of creating a seating plan are usually simple and understandable. As a result, the organizers of the above-mentioned events often decide to create a seating plan by hand, which becomes one of the most time-consuming tasks of the organizers. In this thesis, we defined the arrangement problem and proved it to be NP-complete. Furthermore, we created a web application that allows its users an automatic creation of seating plans. In addition to the automatic creation of seating plans, the application also includes user interfaces for entering the data of the seated persons, for creating seat topologies and for displaying the final seating plan.

Pri analizi podatkov v obliki grafov je iskanje pojavitev manjšega grafa znotraj večjega eden pomembnejših problemov. Rečemo mu problem podgrafnega izomorfizma. V diplomskem delu se posvetimo različici problema, kjer iščemo število vseh induciranih podgrafnih izomorfizmov na neusmerjenih grafih. Opišemo tri sorodne algoritme za reševanje tega problema, ki jih implementiramo in nato paraleliziramo s pomočjo programskega vmesnik OpenMP. Pri paralelizaciji uporabimo pristop z dinamično delitvijo dela, kjer si niti izmenjujejo naloge preko skupne vrste nalog. Za izmenjavo nalog preizkusimo lastno implementacijo vrste in vgrajeno OpenMP-jevo rešitev. Uspešnost paralelizacije eksperimentalno ovrednotimo na dveh testnih množicah. Posvetimo se tudi vplivu granularnosti problema na čas izvajanja. In the analysis of graph data the search for an appearance of a smaller graph within a larger one is one of the more important problems. We call it the subgraph isomorphism problem. In this thesis we focus on a problem variant, where we search for the number of all induced subgraph isomorphisms on undirected graphs. We describe three related algorithms for solving this problem which we implement and then parallelize using an application programming interface called OpenMP. At parallelization we take on the approach of dynamic distribution of tasks where threads exchange tasks through a global queue. For task exchange we test our own implementation of the queue and the built-in OpenMP solution. Parallel algorithms are experimentally evaluated on two test sets. We also examine the impact of granularity on the execution time.

V magistrskem delu obravnavamo problem podgrafnega izomorfizma. Izhajamo iz bolj splošnega ogrodja problemov zadoščanja omejitvam. Predstavimo znane metode sestopanja za reševanje takšnih problemov in jih uporabimo pri reševanju problema podgrafnega izomorfizma. Opišemo nekaj izboljšav teh metod, pri katerih upoštevamo dodatne lastnosti obravnavanega problema. V okviru ogrodja problemov zadoščanja omejitev predstavimo tudi najuspešnejše obstoječe algoritme. Opisane metode implementiramo kot knjižnico v programskem jeziku C++. Implementacijo eksperimentalno ovrednotimo na več javno dostopnih zbirkah testnih primerov, na katerih opravimo tudi primerjavo z obstoječimi algoritmi. Osredotočimo se predvsem na primerjavo hitrosti izvajanja. The master's thesis deals with the subgraph isomorphism problem. We start by considering the more general class of constraint satisfaction problems. We present a backtracking framework for solving such problems and use it to solve the subgraph isomorphism problem. By taking into account the specific properties of our problem, we describe some improvements to the basic methods. The framework is also used to characterize some of the most successful existing algorithms. We have implemented a C++ library of the presented methods. We use it to experimentally evaluate the methods on multiple publicly available data sets and compare them with existing algorithms. The main focus of the comparison is the execution time of the algorithms.

V problemu izomorfizma podgrafov imamo podana dva grafa G in H. Za njiju je potrebno ugotoviti, ali graf G vsebuje podgraf, ki je izomorfen grafu H. Problem je v splošnem NP-poln. V magistrskem delu se omejimo na problem izomorfizmov podgrafov ravninskih grafov. V prvem poglavju so opisani osnovni pojmi in definicije, ki jih potrebujemo v nadaljevanju. V drugem poglavju so najprej opisani drevesna dekompozicija, delni izomorfizem, meja delnega izomorfizma in konsistentnost. Potem je opisan postopek za učinkovito iskanje izomorfizmov podgrafov v ravninskih grafih z omejeno drevesno širino. Nadalje predstavimo, kako pokrijemo poljuben ravninski graf s podgrafi, ki imajo omejeno drevesno širino. Na koncu je podan algoritem za iskanje izomorfizmov podgrafov ravninskih grafov, ki teče v linearnem času za vsak povezan graf H z omejeno velikostjo. In the subgraph isomorphism problem two graphs G and H are given as input. We must determine whether G contains a subgraph isomorphic to H. In general, the problem is NP-complete. In this thesis we present a linear algorithm for the subgraph isomorphism problem in planar graphs. The first section describes the basic concepts and definitions. The second chapter describes the tree decomposition, partial isomorphism, partial isomorphism boundary and consistency. Then it describes how to efficiently search for subgraph isomorphisms in planar graphs with bounded tree-width. Furthermore, we present how to cover any planar graph with subgraphs that have bounded tree-width. At the end, we present an algorithm for subgraph isomorphism problem in planar graphs, which runs in linear time for any connected graph H of a constant size.