Convex geometries are combinatorial structures; they capture in an abstract way the essential features of convexity in Euclidean space, graphs or posets for instance. A convex geometry consists of a finite ground set plus a collection of subsets, called the convex sets and satisfying certain axioms. In this work, we study two natural problems on convex geometries. First, we consider the maximum-weight convex set problem. After proving a hardness result for the problem, we study a special family of convex geometries built on split graphs. We show that the convex sets of such a convex geometry relate to poset convex geometries constructed from the split graph. We discuss a few consequences, obtaining a simple polynomial-time algorithm to solve the problem on split graphs. Next, we generalize those results and design the first polynomial-time algorithm for the maximum-weight convex set problem in chordal graphs. Second, we consider the realizability problem. We show that deciding if a given convex geometry (encoded by its copoints) results from a point set in the plane is ER-hard. We complete our text with a brief discussion of potential further work. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished
| Identifer | oai:union.ndltd.org:ulb.ac.be/oai:dipot.ulb.ac.be:2013/288673 |
| Date | 25 June 2019 |
| Creators | Merckx, Keno |
| Contributors | Cardinal, Jean, Doignon, Jean-Paul, Fiorini, Samuel, Joret, Gwenaël, Langerman, Stefan, Habib, Michel M.A., Queyranne, Maurice |
| Publisher | Universite Libre de Bruxelles, Université libre de Bruxelles, Faculté des Sciences – Informatique, Bruxelles |
| Source Sets | Université libre de Bruxelles |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis, info:ulb-repo/semantics/doctoralThesis, info:ulb-repo/semantics/openurl/vlink-dissertation |
| Format | 3 full-text file(s): application/pdf | application/pdf | application/pdf |
| Rights | 3 full-text file(s): info:eu-repo/semantics/closedAccess | info:eu-repo/semantics/openAccess | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0025 seconds