TY - GEN

T1 - Split-decomposition trees with prime nodes

T2 - 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018

AU - Bahrani, Maryam

AU - Lumbroso, Jérémie

N1 - Publisher Copyright:
© 2018 by SIAM.

PY - 2018

Y1 - 2018

N2 - In this paper, we build on recent results by Chauve et al. and Bahrani and Lumbroso, which combined the splitdecomposition, as exposed by Gioan and Paul, with analytic combinatorics, to produce new enumerative results on graphs-in particular the enumeration of several subclasses of perfect graphs (distance-hereditary, 3-leaf power, ptolemaic). Our goal was to study a simple family of graphs, of which the split-decomposition trees have prime nodes drawn from an enumerable (and manageable!) set of graphs. Cactus graphs, which we describe in more detail further down in this paper, can be thought of as trees with their edges replaced by cycles (of arbitrary lengths). Their split-decomposition trees contain prime nodes that are cycles, making them ideal to study. We derive a characterization for the split-decomposition trees of cactus graphs, produce a general template of symbolic grammars for cactus graphs, and implement random generation for these graphs, building on work by Iriza.

AB - In this paper, we build on recent results by Chauve et al. and Bahrani and Lumbroso, which combined the splitdecomposition, as exposed by Gioan and Paul, with analytic combinatorics, to produce new enumerative results on graphs-in particular the enumeration of several subclasses of perfect graphs (distance-hereditary, 3-leaf power, ptolemaic). Our goal was to study a simple family of graphs, of which the split-decomposition trees have prime nodes drawn from an enumerable (and manageable!) set of graphs. Cactus graphs, which we describe in more detail further down in this paper, can be thought of as trees with their edges replaced by cycles (of arbitrary lengths). Their split-decomposition trees contain prime nodes that are cycles, making them ideal to study. We derive a characterization for the split-decomposition trees of cactus graphs, produce a general template of symbolic grammars for cactus graphs, and implement random generation for these graphs, building on work by Iriza.

UR - http://www.scopus.com/inward/record.url?scp=85043465698&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85043465698&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975062.13

DO - 10.1137/1.9781611975062.13

M3 - Conference contribution

AN - SCOPUS:85043465698

T3 - 2018 Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018

SP - 143

EP - 157

BT - 2018 Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018

A2 - Nebel, Markus

A2 - Wagner, Stephan

PB - Society for Industrial and Applied Mathematics Publications

Y2 - 8 January 2018 through 9 January 2018

ER -