Köln, University, Diss., 2004.

Zugl.: Jena, Univ., Diss., 2009

Konstanz, Univ., Diplomarb., 2005.

Given graphs G,H, is it possible to find a matching which, when deleted from G, destroys all copies of H? The answer is obvious for some inputs—notably, when G is a large complete graph the answer is “no”—but in general this can be a very difficult question. In this thesis, we study this decision problem when H is a fixed tree or cycle; our aim is to identify those H for which it can be solved efficiently. The H-transverse matching problem, TM(H) for short, asks whether an input graph admits a matching M such that no subgraph of G − M is isomorphic to H. The main goal of this thesis is the following dichotomy. When H is a triangle or one of a few small-diameter trees, there is a polynomial-time algorithm to find an H-transverse matching if one exists. However, TM(H) is NP-complete when H is any longer cycle or a tree of diameter ≥ 4. In addition, we study the restriction of these problems to structured graph classes. / Graduate

Diss. no. 13266 techn. sc. SFIT Zurich. / Im Buchh.: Aachen : Shaker. Literaturverz.

Matching of concepts with variables (concept patterns) is a relatively new operation that has been introduced in the context of description logics, originally to help filter out unimportant aspects of large concepts appearing in industrial-strength knowledge bases. Previous work has concentrated on (sub-)languages of CLASSIC, which in particular do not allow for existential restrictions. In this work, we present sound and complete decision algorithms for the solvability of matching problems and for computing sets of matchers for matching problems in description logics with existential restrictions.

近年來，越來越多單身男女希望能夠透過網路交友平台找到自己的另一半。本論文考慮一個網路交友平台的經營，期望能夠讓每位參與者都找到適合彼此的另一半。我們使用工作指派問題的數學模型整合配對問題及穩定室友問題的概念建構男女配對問題的數學模型。並且考慮多位交友對象、拒絕對象與分級制度等問題，分別提出不同的數學模型。最後，我們使用隨機產生的資料模擬參與者的雙向配度，以GAMS軟體求解，分析不同的配對結果，亦探討不同模型的難易度及求解所需之運算時間。 / In recent years, more and more single women and men hope that they can find their Mr. or Mrs. Right through the internet dating platform. This paper considers the operation of an internet dating platform which expects each participant to find the other half of each other. We propose mathematical models of the women and men matching problem by using the mathematical model of the assignment problem and integrating the idea of matching problem as well as the stable roommate problem. We also consider the problems of multiple dating objects, matching with rejection, and classification member. Finally, a simulate study will be performed by using the randomly generating data to simulate the two-way matching degree of each pair of participants. We analyze the different matching results obtained by the different models. We also present the difficulty of different models and the solution times.

Matching of concepts against patterns is a new inference task in Description Logics, which was originally motivated by applications of the CLASSIC system. Consequently, the work on this problem was until now mostly concerned with sublanguages of the Classic language, which does not allow for existential restrictions. Motivated by an application in chemical process engineering, which requires a description language with existential restrictions, this paper investigates the matching problem in Description Logics with existential restrictions. It turns out that existential restrictions make matching more complex in two respects. First, whereas matching in sublanguages of CLASSIC is polynomial, deciding the existence of matchers is an NP-complete problem in the presence of existential restrictions. Second, whereas in sublanguages of Classic solvable matching problems have a unique least matcher, this is not the case for languages with existential restrictions. Thus, it is not a priori clear which of the (possibly infinitely many) matchers should be returned by a matching algorithm. After determining the complexity of the decision problem, the present paper first investigates the question of what are 'interesting' sets of matchers, and then describes algorithms for computing these sets for the languages EL (which allows for conjunction and existential restrictions) and ALE (which additionally allows for value restrictions, primitive negation, and the bottom concept). / An abridged version of this technical report has been submitted to KR 2000.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:31:58Z No. of bitstreams: 2 Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:35:15Z (GMT) No. of bitstreams: 2 Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2016-03-17T17:35:15Z (GMT). No. of bitstreams: 2 Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2011-02-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work considers three relevant NP-hard problems. The firstone is the one-dimensional cutting stock problem in which the non-used material in the cutting patterns may be used in the future. For this problem we analyze the existing mathematical models, propose new models, design a heuristic and two metaheuristic approaches, being their performances improved by using parallel programming, and solve instances, practical and randomly generated, from the literature. The computational experiments were quite good for all tested instances. The second problem we consider is the stable roommates problem (a variant of the stable matching problem). For this we give two mathematical programming models, sequential and parallel implementations of a Tabu Search, and a Branch-andBound. Also, we report computational experiments to instances of the problem. The last problem we consider is the compartmentalized knapsack problem (a generalization of the knapsack problem) for which we analyze a quadratic integer model and give a linear integer model. We design a greedy heuristic and a GRASP algorithm, that uses path-relinking, and solve randomly generated instances. All parallel implementations use Graphics Processing Units (GPUs). / Este trabalho considera três problemas, NP-difíceis, relevantes de estudo em otimização combinatória. O primeiro deles é o problema de corte uni-dimensional de objetos, onde o material não usado pelos padrões de corte pode ser usado no futuro. Para este problema analisamos os modelos matemáticos existentes, propomos novos modelos, projetamos uma heurística construtiva e duas metaheurísticas, sendo seus desempenhos melhorados com programação paralela, e resolvemos instâncias, práticas e aleatórias, encontradas na literatura; sendo os experimentos computacionais muito bons para todas as intânciastestadas.Osegundoproblemaqueconsideramoséoproblemadoscompanheiros estáveis (stable roommates problem), uma variante do problema de emparelhamento estável (stable matching problem). Para este propomos dois modelos matemáticos, uma implementação sequencial e uma paralela de uma Tabu Search, e um Branch-andBound. Também reportamos experimentos computacionais para instâncias do problema. O último problema considerado é o da mochila compartimentada (uma generalização do problema clássico da mochila), para o qual analisamos uma modelagem quadrática inteira e propomos um modelo linear inteiro; também projetamos uma heurística gulosa, um algoritmo GRASP, que usa path-relinking, e resolvemos intâncias geradas aleatóriamente. Todas as implementações em paralelo usam unidades de processamento gráfico (Graphics Processing Units, GPUs).

University, Diss., 2004--Saarbrücken.