Skip to Main content Skip to Navigation
Reports

Stable set meeting every longest paths

Frédéric Havet 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Laborde, Payan and Xuong conjectured that every digraph has a stable set meeting every longest path. We prove that this conjecture holds for digraphs with stability at most 2.
Keywords : LONGEST PATH STABLE SET INDEPENDANT SET CHROMATIC NUMBER
Document type :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
https://hal.inria.fr/inria-00071575
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:00:59 PM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:26:18 PM

Files

Vignette du document
RR-5009.pdf

Identifiers

  • HAL Id : inria-00071575, version 1

Collections

INRIA | INRIA-RRRT | CNRS | UNICE | I3S | LARA | UNIV-COTEDAZUR

Citation

Frédéric Havet. Stable set meeting every longest paths. RR-5009, INRIA. 2003. ⟨inria-00071575⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

380

Files downloads

243

 

Contact                    Legal Notice                    Personal Data