Thumbnail - Request a copy

On the star forest polytope

Aoudia, Lamia; Nguyen, Viet Hung; Mahjoub, Ali Ridha; Aider, Meziane (2014-11), On the star forest polytope, in Kacem, Imed; Laroche, Pierre; Róka, Zsuzsanna, 2014 International Conference on Control, Decision and Information Technologies (CoDIT). Proceedings, IEEE : Piscataway, NJ, p. 263-268. 10.1109/CoDIT.2014.6996904

Type
Communication / Conférence
Date
2014-11
Conference title
2014 International Conference on Control, Decision and Information Technologies (CoDIT)
Conference date
2014-11
Conference city
Metz
Conference country
France
Book title
2014 International Conference on Control, Decision and Information Technologies (CoDIT). Proceedings
Book author
Kacem, Imed; Laroche, Pierre; Róka, Zsuzsanna
Publisher
IEEE
Published in
Piscataway, NJ
ISBN
978-1-4799-6773-5
Number of pages
794
Pages
263-268
Publication identifier
Metadata
Show full item record
Author(s)
Aoudia, Lamia

Nguyen, Viet Hung
Laboratoire d'Informatique de Paris 6 [LIP6]
Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Aider, Meziane
Abstract (EN)
A star forest is a collection of vertex-disjoint trees of depth at most 1, and its size is the number of leaves in all its components. A spanning star forest of a given graph G is a spanning subgraph of G that is also star forest. The spanning star forest problem (SSFP for short) [10] is to find maximum size spanning star forest of given graph. Let define some graph G = (V;E), to every star forest we associate a vector xF . xF (e) = 1 if e ∈ F and xF (e) = 0 otherwise. xF is the incident vector of spanning star forest F. The convex hull of all spanning star forest incident vectors is called a spanning star forest polytope, denoted SFP(G). In this paper we are mainly interested on complete characterization of SFP(G).
Subjects / Keywords
vectors; trees (mathematics); polytope; graph; star forest
JEL
C02 - Mathematical Methods