Browsing Department of Informatics by Author "Samer, Phillippe"
Now showing items 1-6 of 6
-
Fixed cardinality stable sets
Samer, Phillippe; Haugland, Dag (Journal article; Peer reviewed, 2021)Given an undirected graph G=(V,E) and a positive integer k in {1, ..., |V|}, we initiate the combinatorial study of stable sets of cardinality exactly k in G. Our aim is to instigate the polyhedral investigation of the ... -
Polyhedra and algorithms for problems bridging notions of connectivity and independence
Samer, Phillippe (Doctoral thesis, 2023-12-21)I denne avhandlinga interesserer vi oss for å finne delgrafer som svarer til utvalgte modeller for begrepene sammenheng og uavhengighet. I korthet betyr dette stabile (også kalt uavhengige) mengder med gitt kardinalitet, ... -
Polyhedral approach to weighted connected matchings in general graphs
Samer, Phillippe; Moura, Phablo F S (Journal article; Peer reviewed, 2024)A connected matching in a graph G consists of a set of pairwise disjoint edges whose covered vertices induce a connected subgraph of G. While finding a connected matching of maximum cardinality is a well-solved problem, ... -
Polyhedral results and stronger Lagrangean bounds for stable spanning trees
Samer, Phillippe; Haugland, Dag (Journal article; Peer reviewed, 2023)Given a graph G=(V,E) and a set C of unordered pairs of edges regarded as being in conflict, a stable spanning tree in G is a set of edges T inducing a spanning tree in G, such that for each {ei,ej}∈C, at most one of the ... -
Towards stronger Lagrangean bounds for stable spanning trees
Samer, Phillippe; Haugland, Dag (Chapter, 2022)Given a graph G=(V,E) and a set C of unordered pairs of edges regarded as being in conflict, a stable spanning tree in G is a set of edges T inducing a spanning tree in G, such that for each {e_i, e_j} in C, at most one ... -
The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope
Samer, Phillippe; Haugland, Dag (Chapter, 2021)Given an undirected graph G = (V, E) and an integer k∈{1,…,|V|} , we initiate the combinatorial study of stable sets of cardinality exactly k in G. Our aim is to instigate the polyhedral investigation of the convex hull ...