Entropic Uniform Sampling of Linear Extensions in Series-Parallel Posets

被引：5

作者：

Bodini, Olivier ^{[1
]}

Dien, Matthieu ^{[2
]}

Genitrini, Antoine ^{[2
]}

Peschanski, Frederic ^{[2
]}

机构：

[1] Univ Paris Nort, Inst Galilee, Lab Informat Paris Nort, CNRS,UMR 7030, 99 Ave Jean Baptiste Clement, F-93430 Villetaneuse, France

[2] UPMC Univ Paris 06, Sorbonne Univ, CNRS, LIP6,UMR 7606, 4 Pl Jussieu, F-75005 Paris, France

来源：

COMPUTER SCIENCE - THEORY AND APPLICATIONS (CSR 2017) | 2017年 / 10304卷

关键词：

D O I：

10.1007/978-3-319-58747-9_9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we introduce a uniform random sampler for linear extensions of Series-Parallel posets. The algorithms we present ensure an essential property of random generation algorithms: entropy. They are in a sense optimal in their consumption of random bits.

引用

页码：71 / 84

页数：14

共 11 条

[1]

Bodini O, 2016, ELECTRON J COMB, V23

[2]

Felsner S, 1997, PROCEEDINGS OF THE EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P239

[3]

Flajolet P., 2009, Analytic Combinatorics, Vfirst

[4] Fast perfect sampling from linear extensions [J].

Huber, Mark .

DISCRETE MATHEMATICS, 2006, 306 (04) :420-428

[5]

Klein P.N., Optimization algorithms for planar graphs

[6]

Mohring R. H., 1987, COMPUTATIONALLY TRAC

[7]

Sedgewick R., 2008, DAGST WORKSH DAT STR, P17

[8] A MATHEMATICAL THEORY OF COMMUNICATION [J].

SHANNON, CE .

BELL SYSTEM TECHNICAL JOURNAL, 1948, 27 (04) :623-656

[9]

Stanley R.P., 2011, Enumerative combinatorics, V1

[10]

Valdes J, 1979, P 11 ANN ACM S THEOR, P1, DOI DOI 10.1145/800135.804393

← 1 2 →