Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 15 min ago
PreprintCC BY 4.0HAL

Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph

  • François Clautiaux
  • Pierre Pesneau
Open at sourcePDFCite

Abstract

we study two families of MIP formulations for the maximum chordal subgraph

• we provide a theoretical study of the chordal subgraph polytope • we introduce two families of valid inequalities, characterize when they are facet-defining, and develop heuristic separation algorithms for each.

• We provide computational experiments on classical benchmarks from the literature

Related

  1. Subgraph Isomorphism, Integer Linear Programming, and Lattices: A Linear Algebraic Framework
    Bryant Gipson
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  2. Computing Equilibria in Integer Programming Games with Shared Constraints
    Bainian Hao, Hyunwoo Lee, Robert Hildebrand +1
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  3. Computing Approximate Solutions of Inconsistent Max-Min Fuzzy Relational Equations by Mixed-Integer Programming
    Ismaïl Baaj
    HALPreprintCC BY 4.0Full textStatisticsHAL
  4. Physics-Informed Mixed Integer Programming Methods for Optimal Patch Antennas
    Ruben Hoeksma, Jesse van Rhijn, Marc Uetz +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
    Cinar Ari, Robert Hildebrand
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{clautiaux2026integer,
  title = {{Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph}},
  author = {François Clautiaux and Pierre Pesneau},
  howpublished = {HAL},
  year = {2026},
  month = oct,
  url = {https://inria.hal.science/hal-05773479v1},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
AU  - François Clautiaux
AU  - Pierre Pesneau
PY  - 2026
DA  - 2026/10/01
PB  - HAL
UR  - https://inria.hal.science/hal-05773479v1
AB  - we study two families of MIP formulations for the maximum chordal subgraph  • we provide a theoretical study of the chordal subgraph polytope • we introduce two families of valid inequalities, characterize when they are facet-defining, and develop heuristic separation algorithms for each.  • We provide computational experiments on classical benchmarks from the literature
ER  -