Enumerating and constructing essentially equivalent lattice paths (Q2765090)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Enumerating and constructing essentially equivalent lattice paths |
scientific article; zbMATH DE number 1693694
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Enumerating and constructing essentially equivalent lattice paths |
scientific article; zbMATH DE number 1693694 |
Statements
6 June 2002
0 references
independence number
0 references
lattice paths
0 references
greedy algorithm
0 references
Enumerating and constructing essentially equivalent lattice paths (English)
0 references
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.
0 references
