Geodesic
On the shelling antimatroids of split graphs
Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1.

Voir la notice de l'article provenant de la source Episciences

Chordal graph shelling antimatroids have received little attention with regard to their combinatorial properties and related optimization problems, as compared to the case of poset shelling antimatroids. Here we consider a special case of these antimatroids, namely the split graph shelling antimatroids. We show that the feasible sets of such an antimatroid relate to some poset shelling antimatroids constructed from the graph. We discuss a few applications, obtaining in particular a simple polynomial-time algorithm to find a maximum weight feasible set. We also provide a simple description of the circuits and the free sets. 
@article{DMTCS_2017_19_1_a4,
     author = {Cardinal, Jean and Doignon, Jean-Paul and Merckx, Keno},
     title = {On the shelling antimatroids of split graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-1-7},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-7/}
}
TY  - JOUR
AU  - Cardinal, Jean
AU  - Doignon, Jean-Paul
AU  - Merckx, Keno
TI  - On the shelling antimatroids of split graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-7/
DO  - 10.23638/DMTCS-19-1-7
LA  - en
ID  - DMTCS_2017_19_1_a4
ER  - 
%0 Journal Article
%A Cardinal, Jean
%A Doignon, Jean-Paul
%A Merckx, Keno
%T On the shelling antimatroids of split graphs
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-7/
%R 10.23638/DMTCS-19-1-7
%G en
%F DMTCS_2017_19_1_a4
Cardinal, Jean; Doignon, Jean-Paul; Merckx, Keno. On the shelling antimatroids of split graphs. Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1. doi : 10.23638/DMTCS-19-1-7. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-7/

Cité par Sources :