National Repository of Grey Literature 2 records found  Search took 0.01 seconds. 
Rozklady propojovacích sítí na dlouhé cesty
Měkuta, Kryštof ; Gregor, Petr (advisor) ; Dvořák, Tomáš (referee)
❚✐t❧❡✿ P❛rt✐t✐♦♥s ♦❢ ✐♥t❡r❝♦♥♥❡❝t✐♦♥ ♥❡t✇♦r❦s ✐♥t♦ ❧♦♥❣ ♣❛t❤s ❆✉t❤♦r✿ ❑r②➨t♦❢ ▼➙❦✉t❛ ❉❡♣❛rt♠❡♥t✿ ❉❡♣❛rt♠❡♥t ♦❢ ❚❤❡♦r❡t✐❝❛❧ ❈♦♠♣✉t❡r ❙❝✐❡♥❝❡ ❛♥❞ ▼❛t❤❡♠❛t✐❝❛❧ ▲♦❣✐❝ ❙✉♣❡r✈✐s♦r✿ ▼❣r✳ P❡tr ●r❡❣♦r✱ P❤✳❉✳✱ ❑❚■▼▲ ❆❜str❛❝t✿ ❲❡ s✉r✈❡② s♦♠❡ ❜❛s✐❝ ♣r♦♣❡rt✐❡s ♦❢ s❡❧❡❝t❡❞ ✐♥t❡r❝♦♥♥❡❝t✐♦♥ ♥❡t✇♦r❦s✱ ♠♦r❡ ♣r❡❝✐s❡❧② ♠♦❞✐✜❝❛t✐♦♥s ♦❢ ❤②♣❡r❝✉❜❡s✳ ■♥ ♣❛rt✐❝✉❧❛r✱ ✇❡ st✉❞② ❢❛✉❧t✲t♦❧❡r❛♥❝❡ ♦❢ ❛✉❣♠❡♥t❡❞ ❝✉❜❡s ✇✐t❤ r❡s♣❡❝t t♦ t❤❡ ❡①✐st❡♥❝❡ ♦❢ ❍❛♠✐❧t♦♥✐❛♥ ❝②❝❧❡s✳ ❲❡ ❛❧✲ s♦ ♣r❡s❡♥t ❛ ♠❡t❤♦❞ t♦ ❝♦♥str✉❝t ♠❛♥② s♣❛♥♥✐♥❣ s✉❜❣r❛♣❤s ♦❢ AQn ✐s♦♠♦r♣❤✐❝ t♦ Qn ✉s✐♥❣ ❡❧❡♠❡♥t❛r② ❢❛❝ts ❢r♦♠ ❧✐♥❡❛r ❛❧❣❡❜r❛✳ ❲❡ ♣r♦✈❡ t❤❛t n✲❞✐♠❡♥s✐♦♥❛❧ ❛✉❣♠❡♥t❡❞ ❝✉❜❡ AQn ✇✐t❤ f ❢❛✉❧t② ❡❞❣❡s ❝♦♥t❛✐♥s ❛ ❝♦♣② ♦❢ n✲❞✐♠❡♥s✐♦♥❛❧ ❤②♣❡r✲ ❝✉❜❡ Qn ✇✐t❤ ❛t ♠♦st n 2n−1 f ❢❛✉❧t② ❡❞❣❡s✳ ❯s✐♥❣ t❤✐s r❡s✉❧t ✇❡ ❛r❡ ❛❜❧❡ t♦ ❡❛s✐❧② tr❛♥s❢❡r s❡✈❡r❛❧ ♣r♦♣❡rt✐❡s ♦❢ Qn ✇✐t❤ ❢❛✉❧t② ❡❞❣❡s t♦ AQn ✇✐t❤ ✭♠♦r❡✮ ❢❛✉❧t② ❡❞❣❡s✳ ❆♣♣❧②✐♥❣ s✐♠✐❧❛r ♠❡t❤♦❞✱ ✇❡ ❛❧s♦ s❤♦✇ t❤❛t ✐❢ f ≤ 3n−7 ❛♥❞ ❡✈❡r② ✈❡rt❡① ♦❢ AQn ✐s ✐♥❝✐❞❡♥t t♦ ❛t ❧❡❛st t✇♦ ♥♦♥✲❢❛✉❧t② ❡❞❣❡s✱ t❤❡♥ AQn ❤❛s ❛ ♥♦♥✲❢❛✉❧t② ❤❛♠✐❧t♦♥✐❛♥ ❝②❝❧❡✳ ▼♦r❡♦✈❡r✱ ✇❡ s❤♦✇ t❤❛t ❡✈❡r② t✇♦ ♠♦♥♦♠♦r♣❤✐s♠s ♦❢ G1 t♦ AQn ❛♥❞ G2 t♦ AQm ❝❛♥ ❜❡ ❝♦♠♣♦s❡❞ ✐♥t♦ ❛ ♠♦♥♦♠♦r♣❤✐s♠ ♦❢ t❤❡ ❈❛rt❡s✐❛♥ ♣r♦❞✉❝t G1 G2 t♦ AQn+m✳ ❑❡②✇♦r❞s✿ ❤②♣❡r❝✉❜❡✱ ❛✉❣♠❡♥t❡❞ ❝✉❜❡✱ ❤❛♠✐❧t♦♥✐❝✐t②✱ ❢❛✉❧t② ❡❞❣❡s
Rozklady propojovacích sítí na dlouhé cesty
Měkuta, Kryštof ; Gregor, Petr (advisor) ; Dvořák, Tomáš (referee)
❚✐t❧❡✿ P❛rt✐t✐♦♥s ♦❢ ✐♥t❡r❝♦♥♥❡❝t✐♦♥ ♥❡t✇♦r❦s ✐♥t♦ ❧♦♥❣ ♣❛t❤s ❆✉t❤♦r✿ ❑r②➨t♦❢ ▼➙❦✉t❛ ❉❡♣❛rt♠❡♥t✿ ❉❡♣❛rt♠❡♥t ♦❢ ❚❤❡♦r❡t✐❝❛❧ ❈♦♠♣✉t❡r ❙❝✐❡♥❝❡ ❛♥❞ ▼❛t❤❡♠❛t✐❝❛❧ ▲♦❣✐❝ ❙✉♣❡r✈✐s♦r✿ ▼❣r✳ P❡tr ●r❡❣♦r✱ P❤✳❉✳✱ ❑❚■▼▲ ❆❜str❛❝t✿ ❲❡ s✉r✈❡② s♦♠❡ ❜❛s✐❝ ♣r♦♣❡rt✐❡s ♦❢ s❡❧❡❝t❡❞ ✐♥t❡r❝♦♥♥❡❝t✐♦♥ ♥❡t✇♦r❦s✱ ♠♦r❡ ♣r❡❝✐s❡❧② ♠♦❞✐✜❝❛t✐♦♥s ♦❢ ❤②♣❡r❝✉❜❡s✳ ■♥ ♣❛rt✐❝✉❧❛r✱ ✇❡ st✉❞② ❢❛✉❧t✲t♦❧❡r❛♥❝❡ ♦❢ ❛✉❣♠❡♥t❡❞ ❝✉❜❡s ✇✐t❤ r❡s♣❡❝t t♦ t❤❡ ❡①✐st❡♥❝❡ ♦❢ ❍❛♠✐❧t♦♥✐❛♥ ❝②❝❧❡s✳ ❲❡ ❛❧✲ s♦ ♣r❡s❡♥t ❛ ♠❡t❤♦❞ t♦ ❝♦♥str✉❝t ♠❛♥② s♣❛♥♥✐♥❣ s✉❜❣r❛♣❤s ♦❢ AQn ✐s♦♠♦r♣❤✐❝ t♦ Qn ✉s✐♥❣ ❡❧❡♠❡♥t❛r② ❢❛❝ts ❢r♦♠ ❧✐♥❡❛r ❛❧❣❡❜r❛✳ ❲❡ ♣r♦✈❡ t❤❛t n✲❞✐♠❡♥s✐♦♥❛❧ ❛✉❣♠❡♥t❡❞ ❝✉❜❡ AQn ✇✐t❤ f ❢❛✉❧t② ❡❞❣❡s ❝♦♥t❛✐♥s ❛ ❝♦♣② ♦❢ n✲❞✐♠❡♥s✐♦♥❛❧ ❤②♣❡r✲ ❝✉❜❡ Qn ✇✐t❤ ❛t ♠♦st n 2n−1 f ❢❛✉❧t② ❡❞❣❡s✳ ❯s✐♥❣ t❤✐s r❡s✉❧t ✇❡ ❛r❡ ❛❜❧❡ t♦ ❡❛s✐❧② tr❛♥s❢❡r s❡✈❡r❛❧ ♣r♦♣❡rt✐❡s ♦❢ Qn ✇✐t❤ ❢❛✉❧t② ❡❞❣❡s t♦ AQn ✇✐t❤ ✭♠♦r❡✮ ❢❛✉❧t② ❡❞❣❡s✳ ❆♣♣❧②✐♥❣ s✐♠✐❧❛r ♠❡t❤♦❞✱ ✇❡ ❛❧s♦ s❤♦✇ t❤❛t ✐❢ f ≤ 3n−7 ❛♥❞ ❡✈❡r② ✈❡rt❡① ♦❢ AQn ✐s ✐♥❝✐❞❡♥t t♦ ❛t ❧❡❛st t✇♦ ♥♦♥✲❢❛✉❧t② ❡❞❣❡s✱ t❤❡♥ AQn ❤❛s ❛ ♥♦♥✲❢❛✉❧t② ❤❛♠✐❧t♦♥✐❛♥ ❝②❝❧❡✳ ▼♦r❡♦✈❡r✱ ✇❡ s❤♦✇ t❤❛t ❡✈❡r② t✇♦ ♠♦♥♦♠♦r♣❤✐s♠s ♦❢ G1 t♦ AQn ❛♥❞ G2 t♦ AQm ❝❛♥ ❜❡ ❝♦♠♣♦s❡❞ ✐♥t♦ ❛ ♠♦♥♦♠♦r♣❤✐s♠ ♦❢ t❤❡ ❈❛rt❡s✐❛♥ ♣r♦❞✉❝t G1 G2 t♦ AQn+m✳ ❑❡②✇♦r❞s✿ ❤②♣❡r❝✉❜❡✱ ❛✉❣♠❡♥t❡❞ ❝✉❜❡✱ ❤❛♠✐❧t♦♥✐❝✐t②✱ ❢❛✉❧t② ❡❞❣❡s

Interested in being notified about new results for this query?
Subscribe to the RSS feed.