Return to search

Optimization and Realizability Problems for Convex Geometries

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

Identiferoai:union.ndltd.org:ulb.ac.be/oai:dipot.ulb.ac.be:2013/288673
Date25 June 2019
CreatorsMerckx, Keno
ContributorsCardinal, Jean, Doignon, Jean-Paul, Fiorini, Samuel, Joret, Gwenaël, Langerman, Stefan, Habib, Michel M.A., Queyranne, Maurice
PublisherUniversite Libre de Bruxelles, Université libre de Bruxelles, Faculté des Sciences – Informatique, Bruxelles
Source SetsUniversité libre de Bruxelles
LanguageEnglish
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/doctoralThesis, info:ulb-repo/semantics/doctoralThesis, info:ulb-repo/semantics/openurl/vlink-dissertation
Format3 full-text file(s): application/pdf | application/pdf | application/pdf
Rights3 full-text file(s): info:eu-repo/semantics/closedAccess | info:eu-repo/semantics/openAccess | info:eu-repo/semantics/restrictedAccess

Page generated in 0.0035 seconds