Stable set meeting every longest paths

Frédéric Havet

Reports Year : 2003

Stable set meeting every longest paths

(1)

Frédéric Havet

Function : Author
PersonId : 9383
IdHAL : frederic-havet
ORCID : 0000-0002-3447-8112
IdRef : 110354842

Algorithms, simulation, combinatorics and optimization for telecommunications

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

STABLE SET INDEPENDANT SET CHROMATIC NUMBER LONGEST PATH

Domains

Other [cs.OH]

Fichier principal

RR-5009.pdf (153.77 Ko)

Rapport De Recherche Inria : Connect in order to contact the contributor

https://inria.hal.science/inria-00071575

Submitted on : Tuesday, May 23, 2006-6:00:59 PM

Last modification on : Monday, February 26, 2024-11:22:07 AM

Long-term archiving on: Sunday, April 4, 2010-10:26:18 PM

Dates and versions

inria-00071575 , version 1 (23-05-2006)

Identifiers

HAL Id : inria-00071575 , version 1

Cite

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

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS INRIA INRIA-RRRT I3S INRIA2 LARA UNIV-COTEDAZUR

144 View

105 Download

Stable set meeting every longest paths

Abstract

Keywords

Domains

Dates and versions

Identifiers

Cite

Export

Collections

Share