VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
-
Gray codes avoiding matchings [Elektronski vir]Dimitrov, Darko ...A (cyclic) ▫$n$▫-bit Gray code is a (cyclic) ordering of all ▫$2^n$▫ binary strings of length ▫$n$▫ such that consecutive strings differ in a single bit. Equivalently, an ▫$n$▫-bit Gray code can be ... viewed as a Hamiltonian path of the ▫$n$▫-dimensional hypercube ▫$Q_n$▫, and a cyclic Gray code as a Hamiltonian cycle of ▫$Q_n$▫. In this paper we study Hamiltonian paths and cycles of ▫$Q_n$▫ avoiding a given set of faulty edges that form a matching, briefly called (cyclic) Gray codes faulting a given matching. Given a matching ▫$M$▫ and two wertices ▫$u,v$▫ of ▫$Q_n$▫, ▫$b \ge 4$▫, our main result provides a necessary and sufficient condition, expressed in terms of forbidden configurations for ▫$M$▫, for the existence of a Gray code between ▫$u$▫ and ▫$v$▫ faulting ▫$M$▫. As a corollary, we obtain a similar characterization for a cyclic Gray code faulting ▫$M$▫. In particular, in case that ▫$M$▫ is a perfect matching, ▫$Q_n$▫ has a (cyclic) Gray code faulting ▫$M$▫ if and only if ▫$Q_n - M$▫ is a connected graph. This complements a recent result of Fink, who proved that every perfect matching of ▫$Q_n$▫ can be extended to a Hamiltonian cycle. Furthermore, our results imply that the problem of Hamiltonicity of ▫$Q_n$▫ with faulty edges, which is NP-complete in general, becomes polynomial for up to ▫$2^{n-1}$▫ edges provided they form a matching.Vir: Discrete mathematics & theoretical computer science [Elektronski vir]. - ISSN 1365-8050 (Vol. 11, no. 2, 2009, str. 123-148)Vrsta gradiva - e-članekLeto - 2009Jezik - angleškiCOBISS.SI-ID - 15521369
Avtor
Dimitrov, Darko |
Dvořák, Tomáš, matematik |
Gregor, Petr |
Škrekovski, Riste
Teme
matematika |
teorija grafov |
Grayjeva koda |
hiper kocka |
Hamiltonova pot |
Hamiltonov cikel |
mathematics |
graph theory |
hipercube |
Gray code |
Hamiltonian path |
Hamiltonian cycle |
matching |
fault tolerance
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Dimitrov, Darko | 50728 |
Dvořák, Tomáš, matematik | |
Gregor, Petr | 38085 |
Škrekovski, Riste | 15518 |
Vir: Osebne bibliografije
in: SICRIS
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Naslov za dostavo:
Med podatki člana manjka naslov.
Storitev za pridobivanje naslova trenutno ni dostopna, prosimo, poskusite še enkrat.
S klikom na gumb "V redu" boste potrdili zgoraj izbrano prevzemno mesto in dokončali postopek rezervacije.
S klikom na gumb "V redu" boste potrdili zgoraj izbrano prevzemno mesto in naslov za dostavo ter dokončali postopek rezervacije.
S klikom na gumb "V redu" boste potrdili zgoraj izbrani naslov za dostavo in dokončali postopek rezervacije.
Obvestilo
Trenutno je storitev za avtomatsko prijavo in rezervacijo nedostopna. Gradivo lahko rezervirate sami na portalu Biblos ali ponovno poskusite tukaj kasneje.
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Gradivo iz matične enote je brezplačno. Če je gradivo na mesto prevzema dostavljeno iz drugih enot, lahko knjižnica to storitev zaračuna.
Mesto prevzema | Status gradiva | Rezervacija |
---|
Rezervacija v teku
Prosimo, počakajte trenutek.
Rezervacija je uspela.
Rezervacija ni uspela.
Rezervacija...
Članska izkaznica:
Mesto prevzema: