Split-decomposition trees with prime nodes: Enumeration and random generation of cactus graphs
M Bahrani, J Lumbroso - 2018 Proceedings of the Fifteenth Workshop on …, 2018 - SIAM
2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and …, 2018•SIAM
In this paper, we build on recent results by Chauve et al. and Bahrani and Lumbroso, which
combined the split-decomposition, 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 …
combined the split-decomposition, 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 …
Abstract
In this paper, we build on recent results by Chauve et al. and Bahrani and Lumbroso, which combined the split-decomposition, 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.
Society for Industrial and Applied Mathematics以上显示的是最相近的搜索结果。 查看全部搜索结果