Meze pro vzdálenostně podmíněné značkování grafů

• Název práce v češtině: Meze pro vzdálenostně podmíněné značkování grafů
• Název v anglickém jazyce: Bounds for distance constrained labeling
• Klíčová slova: značkování, teorie grafů, výpočetní složitost
• Klíčová slova anglicky: labeling, graph theory, complexity
• Akademický rok vypsání: 2009/2010
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: doc. RNDr. Jiří Fiala, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 05.11.2009
• Datum zadání: 05.11.2009
• Datum a čas obhajoby: 19.09.2011 00:00
• Datum odevzdání elektronické podoby: 04.08.2011
• Datum odevzdání tištěné podoby: 05.08.2011
• Datum proběhlé obhajoby: 19.09.2011
• Oponenti: prof. Mgr. Zdeněk Dvořák, Ph.D.

Zásady pro vypracování

Hledané očíslování vrcholů grafu přirozenými čísly má splňovat podmínku, že čísla blízkých vrcholů se mají lišit alespoň o předepsaný parametr. Tato tématika byla již pilně studována v souvislosti s problémem přiřazování frekvencí v telekomunikacích. Cílem práce je klasifikovat (nebo odhadnout) nezbytný rozsah značek pro to, aby problém byl buď polynomiálně řešitelný, nebo - jako druhá varianta - aby se stal NP-těžkým. Je možné uvážit i třídy grafů s jednoduchou strukturou: produkty cest a cyklů, mřížky, rovinné grafy, atd.

Seznam odborné literatury

Reinhard Diestel: Graph Theory, Springer-Verlag (1997)

Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad: Graph Classes: A Survey, SIAM (1999)

M. R. Garey, D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman (1979)

další časopisecká literatura dle doporučení školitele