Finding parity difference by involutions
type: Item
instance of: scholarly article
title: Finding parity difference by involutions
zbMATH Open document ID: 0873.05002
DOI: 10.1016/0012-365X(95)00339-X
author: Grzegorz Stachowiak
published in: Discrete Mathematics
publication date: 1997-10-08T00:00:00Z
review text: For a finite set of combinatorial objects (for example the set of linear extensions of a fixed partial order) we look for an algorithm listing these objects one by one, such that consecutive objects differ as little as possible (in the example: by one transposition only). Such a minimal change generating algorithm defines a hamiltonian path in the graph \(G\) on the set of objects in which two objects are adjacent if and only if they differ by a minimal change. If this minimal change graph is bipartite, then a necessary condition for the existence of a hamiltonian path (or a minimal change generating algorithm) is that the size of the partite sets (colour classes) differs by at most one. This paper shows that computing this parity difference for linear extensions of posets is in GapP and \#P-hard (\#P is not closed under difference, unless PH collapses to UP [\textit{M. Ogiwara} and \textit{L. A. Hemachandra}, J. Comput. Syst. Sci. 46, 295-325 (1993; Zbl 0798.68060)]). The main part of the paper deals with the generation of trees. Let \(\vec{n} = (n_0,n_1,\ldots,n_k)\) and \(n = n_0+n_1+\cdots+n_k\). By \({\mathcal T}(\vec{n})\) we denote the set of strings \(A=a_1a_2a_3\ldots a_n\) consisting of \(n_i\) characters \(i\) for \(i=1,\ldots,k\) such that \(a_1+a_2+\cdots+a_j \leq j\) for all \(j=1,\ldots,n\). Again, a minimal change for such a multiset permutation \(A\) is a transposition of two consecutive characters in the string \(A\). The paper extends a result obtained by \textit{D. W. Ko} and \textit{F. Ruskey} [Discrete Math. 71, No. 1, 47-56 (1988; Zbl 0689.05007)] on the parity difference of \({\mathcal T}(\vec{n})\).
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 68R05
zbMATH DE Number: 1018624
zbMATH Keywords: generation algorithm
zbMATH Keywords: combinatorial objects
zbMATH Keywords: minimal change generating algorithm
zbMATH Keywords: hamitonian path
zbMATH Keywords: minimal change graph
zbMATH Keywords: colour classes
zbMATH Keywords: linear extensions of posets
zbMATH Keywords: multiset permutation
zbMATH Keywords: generation of trees
MaRDI profile type: Publication
cites work: Efficient generation of the binary reflected gray code and its applications
cites work: Counting linear extensions
cites work: Gray codes with restricted density
cites work: Generation of Permutations by Adjacent Transposition
cites work: Solution of some multi-dimensional lattice path parity difference recurrence relations
cites work: Q4207901
cites work: Generating linear extensions of posets by transpositions
cites work: Hamilton Paths in Graphs of Linear Extensions for Unions of Posets
cites work: Q3726126
cites work: One hundred problems in elementary mathematics. With a foreword by Martin Gardner
cites work: Generating Trees and Other Combinatorial Objects Lexicographically
Wikidata QID: Q127754149
Recommended article: Q3796773
Recommended article: Generating binary trees by transpositions
Recommended article: Q3332267
Recommended article: Some Hamilton Paths and a Minimal Change Algorithm
Recommended article: Q3791180
Recommended article: Binary tree gray codes
Recommended article: Q4848760
Recommended article: Adjacent interchange generation of combinations
Recommended article: Q3779757
description: scientific article; zbMATH DE number 1018624