Home > Search Results: keywords:"problém Ruskey - Savage"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.01 seconds. 
Construction of Gray codes with special properties
 Novotný, Tomáš ; Dvořák, Tomáš (advisor) ; Fink, Jiří (referee)
A (cyclic) Gray code is a (cyclic) sequence of all n-bit strings in which consecutive strings differ in a single bit. Ruskey and Savage in 1993 asked whether every matching in a hypercube can be extended to a cyclic Gray code. An affirmative answer is known for perfect matchings (Fink, 2007) while the ge- neral case is still open. The main contribution of this thesis is a generalization of Fink's result to Gray codes with prescribed ends. The characterization of perfect matchings extendable in this way is verified for n = 5 with the assistance of a com- puter, which is useful as a basis for the inductive proof of the general statement. The other part of the thesis is focused on smallest maximal matchings in hyper- cubes which could possibly form especially hard instances of the Ruskey-Savage problem. We devise a novel method which provides - in particular for small di- mensions - maximal matchings of smaller size than the classical asymptotically optimal construction (Forcade, 1973). An adjusted program from the first part is then applied to test the Ruskey-Savage problem over these matchings, however, the extending Gray code is always discovered. 1
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English