Enumerating and constructing essentially equivalent lattice paths
type: Item
instance of: scholarly article
zbMATH Open document ID: 0986.05008
author: Rick Gillman
publication date: 2002-06-06T00:00:00Z
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 1693694
zbMATH Keywords: independence number
zbMATH Keywords: lattice paths
zbMATH Keywords: greedy algorithm
MaRDI profile type: Publication
title: Enumerating and constructing essentially equivalent lattice paths
published in: Geombinatorics
review text: The paper considers lattice paths from \((0,0)\) to \((m,n)\). The following problem is studied: what is the maximum size of a set of such lattice paths, such that any two lattice paths share at most \(k\) edges? The following conjecture is found: a maximum size set is achieved, if all lattice paths are listed in reverse lexicographic order, and one selects paths from this list with a greedy algorithm. (Denoting a step up by N, and a step to the right by E, the reverse lexicographic order of lattice paths from \((0,0)\) to \((2,2)\) is NNEE, NENE, NEEN, ENNE, ENEN, EENN.) Some partial results are given which support this conjecture.
reviewed by: László A. Székely
description: scientific article; zbMATH DE number 1693694