✦ LIBER ✦

Efficient generation of graphical partitions

✍ Scribed by Tiffany M. Barnes; Carla D. Savage

Book ID: 104294793
Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 578 KB
Volume: 78
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(97)00022-x

No coin nor oath required. For personal study only.

✦ Synopsis

Given a positive even integer n, we show how to generate the set G(n) of graphical partitions of n, that is, those partitions of n which correspond to the degree sequences of simple, undirected graphs. The algorithm is based on a recurrence for G(n), and the total time used by the algorithm, independent of output, is 0( IG(n)l), which is constant average time per graphical partition. This is the first algorithm shown to achieve such efficiency for generating G(n) and the direct approach differs from earlier 'generate and reject' schemes and the 'interval/gap' approach.

📜 SIMILAR VOLUMES

Structured generation and manipulation o

Structured generation and manipulation of graphical objects

✍ H. Grauer; W. Müller; V. Jarsch 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 242 KB

Efficient adaptive-shape partitioning of

Efficient adaptive-shape partitioning of video

✍ Kenneth Vermeirsch; Jan De Cock; Stijn Notebaert; Peter Lambert; Joeri Barbarien 📂 Article 📅 2010 🏛 Springer US 🌐 English ⚖ 993 KB

Generating partitions of Markov endomorp

Generating partitions of Markov endomorphisms

✍ B. A. Rubshtein 📂 Article 📅 1974 🏛 Springer US 🌐 English ⚖ 167 KB

A graphical characterization of the effi

A graphical characterization of the efficient set for

✍ Francisco Ruiz; Lourdes Rey; María del Mar Muñoz 📂 Article 📅 2008 🏛 Springer US 🌐 English ⚖ 432 KB

Efficient generation of lexical analyser

Efficient generation of lexical analysers

✍ J. Grosch 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 716 KB

Efficient generation of plane trees

✍ Shin-ichi Nakano 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 96 KB

A rooted plane tree is a rooted tree with a left-to-right ordering specified for the children of each vertex. In this paper we give a simple algorithm to generate all rooted plane trees with at most n vertices. The algorithm uses O(n) space and generates such trees in O(1) time per tree without dupl