Jean Cardinal ; Jean-Paul Doignon ; Keno Merckx - On the shelling antimatroids of split graphs

dmtcs:1349 - Discrete Mathematics & Theoretical Computer Science, March 24, 2017, Vol. 19 no. 1 -
On the shelling antimatroids of split graphsArticle

Authors: Jean Cardinal ; Jean-Paul Doignon ; Keno Merckx

    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.

    Volume: Vol. 19 no. 1
    Section: Combinatorics
    Published on: March 24, 2017
    Accepted on: March 11, 2017
    Submitted on: March 17, 2017
    Keywords: Computer Science - Discrete Mathematics,Computer Science - Data Structures and Algorithms,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 661 times.
    This article's PDF has been downloaded 378 times.