Gray codes for non-crossing partitions and dissections of a convex polygon

被引：9

作者：

Huemer, Clemens ^{[1
]}

Hurtado, Ferran ^{[1
]}

Noy, Marc ^{[1
]}

Omana-Pulido, Elsa ^{[2
]}

机构：

[1] Univ Politecn Cataluna, Dept Matemat Aplicada 2, Barcelona 08034, Spain

[2] Univ Autonoma Metropolitana, Mexico City, DF, Mexico

来源：

DISCRETE APPLIED MATHEMATICS | 2009年 / 157卷 / 07期

关键词：

Gray code; Hamiltonian cycle; Non-crossing partition; Polygon dissection; GRAPHS; TRIANGULATIONS; CONFIGURATIONS; COMBINATIONS; TREE;

D O I：

10.1016/j.dam.2008.06.018

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper we develop Gray codes for two families of geometric objects: non-crossing partitions and dissections of a convex polygon by means of non-crossing diagonals. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：1509 / 1520

页数：12

共 18 条

[1] Minimal change list for Lucas strings and some graph theoretic consequences [J].

Baril, JL ;

Vajnovszki, V .

THEORETICAL COMPUTER SCIENCE, 2005, 346 (2-3) :189-199

[2] Gray code for derangements [J].

Baril, JL ;

Vajnovszki, V .

DISCRETE APPLIED MATHEMATICS, 2004, 140 (1-3) :207-221

[3] LOOPLESS ALGORITHMS FOR GENERATING PERMUTATIONS, COMBINATIONS, AND OTHER COMBINATORIAL CONFIGURATIONS [J].

EHRLICH, G .

JOURNAL OF THE ACM, 1973, 20 (03) :500-513

[4] Analytic combinatorics of non-crossing configurations [J].

Flajolet, P ;

Noy, M .

DISCRETE MATHEMATICS, 1999, 204 (1-3) :203-229

[5]

GAO J, 2005, PUBLICATIONS I MATH, V92, P87

[6] Graphs of non-crossing perfect matchings [J].

Hernando, C ;

Furtado, F ;

Noy, M .

GRAPHS AND COMBINATORICS, 2002, 18 (03) :517-532

[7] Geometric tree graphs of points in convex position [J].

Hernando, MC ;

Hurtado, F ;

Márquez, A ;

Mora, M ;

Noy, M .

DISCRETE APPLIED MATHEMATICS, 1999, 93 (01) :51-66

[8] Graph of triangulations of a convex polygon and tree of triangulations [J].

Hurtado, F ;

Noy, M .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1999, 13 (03) :179-188

[9]

Kaye R., 1976, Information Processing Letters, V5, P171, DOI 10.1016/0020-0190(76)90014-4

[10] Antipodal gray codes [J].

Killian, CE ;

Savage, CD .

DISCRETE MATHEMATICS, 2004, 281 (1-3) :221-236

← 1 2 →