Cristin-resultat-ID: 1940908
Sist endret: 17. januar 2022, 18:36
NVI-rapporteringsår: 2021
Resultat
Vitenskapelig artikkel
2021

Fixed cardinality stable sets

Bidragsytere:
  • Phillippe Samer og
  • Dag Haugland

Tidsskrift

Discrete Applied Mathematics
ISSN 0166-218X
e-ISSN 1872-6771
NVI-nivå 1

Om resultatet

Vitenskapelig artikkel
Publiseringsår: 2021
Publisert online: 2021
Trykket: 2021
Volum: 303
Sider: 137 - 148

Importkilder

Scopus-ID: 2-s2.0-85100388380

Klassifisering

Vitenskapsdisipliner

Teoretisk databehandling, programmeringsspråk og -teori • Algoritmer og beregnbarhetsteori • Matematikk og naturvitenskap

Emneord

Kombinatorisk optimalisering • Matematisk optimering • Diskret matematikk

Beskrivelse Beskrivelse

Tittel

Fixed cardinality stable sets

Sammendrag

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 convex hull of fixed cardinality stable sets, inspired by the rich theory on the classical structure of stable sets. We introduce a large class of valid inequalities to the natural integer programming formulation of the problem. We also present simple combinatorial relaxations based on computing maximum weighted matchings, which yield dual bounds towards finding minimum-weight fixed cardinality stable sets, and particular cases which are solvable in polynomial time.

Bidragsytere

Aktiv cristin-person

Phillippe Samer Lallo Dias

Bidragsyterens navn vises på dette resultatet som Phillippe Samer
  • Tilknyttet:
    Forfatter
    ved Institutt for informatikk ved Universitetet i Bergen

Dag Haugland

  • Tilknyttet:
    Forfatter
    ved Institutt for informatikk ved Universitetet i Bergen
1 - 2 av 2