ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS

Jana Tabea Cslovjecsek
2023
Article

Résumé

We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying alpha

Source officielle

https://infoscience.epfl.ch/record/308035?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.

Results on Sparse Integer Programming and Geometric Independent Sets

Maximum Independent Set: Self-Training through Dynamic Programming

Maximum Independent Set: Self-Training through Dynamic Programming

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.

Results on Sparse Integer Programming and Geometric Independent Sets