Разширени теми в графика алгоритми

Този архив съдържа материали за курса "Разширени теми в графика алгоритми" © преподавани от Рон Шамир в департамента по компютърни науки от Университета в Тел-Авив, на 10/91-2/92 (Есен 92), 4-6/94 (Пролет 94) и 4-6/97 (Пролет 97). Това е един учебен срок завършил курс отвори също да възрастните хора, с една тричасова среща всяка седмица.

Курсът подчерта, алгоритмични и структурни аспекти на "хубави" графиката семейства, по-специално перфектни графики, интервал на графики, хордал графики и съпоставимост графики.

През есента 92 курса се основава до голяма степен на класическата книга на Martin C. Golumbic "Алгоритмичната графика теория и перфектни графики" (Academic Press, 1980), а в някои части също върху ръкописа "Изкуството на комбинаторика", от Douglas B. West.

Пролет 94 и пролет 97 курса имаше подобна основа, но подчерта, по-скорошен материал, и направи много позоваване на приложения в областта на молекулярната биология. (Вижте уеб страницата Алгоритми за молекулярната биология за много повече от тези аспекти.)

Достъпно материал:

  • Подробен преглед разбира се

Пролет 97 (HTML)

Пролет 94 (ASCII)

Есен 92 (ASCII)

  • Пролет 1997 разбира материал (неорганизирани; някои връзки не са актуализирани и някои материали може да се чете само на TAU браузъри съжаление)

Разбира официална уеб страница

Разбира активна уеб страница

  • Книжници пролетта 94 лекции

Разговорите са били предписани от студентите и ревизирани от преподавателя. Пълният набор от бележки впоследствие беше редактирано и форматирани от Sariel Har-Peled. Благодаря, Сариел!

Можете да изтеглите пълните бележките като един послепис файл (150 страници) или всяка лекция отделно.

Капак

  • Заглавна страница
  • Съдържание
  • Списък на фигурите

Лекция #1: Въведение в теорията на графите

  • Основни понятия и означения
  • Пресечни графики
  • Кръгов-дъгови графики
  • Интервал графики
  • Линейни графики на двустранния графики

Лекция #2: Перфектни графики

  • Определяне на перфектната графика
  • Някои определения и свойства
  • Перфектен графика теорема

Лекция #3: Перфектни и триангулирана графики

  • Перфектни графики
    • $ Р $ -Critical графики
    • А многостенна характеризиране на перфектни графики
    • Силна перфектна графика предположенията за
  • Триангулирана графики
    • Въведение
    • Характеризиране триангулирана графики
    • Признавайки триангулирана графики
    • Сложност на времето

Лекция #4: Признавайки триангулирана графики

  • Признавайки триангулирана графики
    • Генериране на ПЕО
    • Тестване схема на елиминиране
      • Наивно алгоритъм
      • Ефективно алгоритъм
      • Пример
      • Коректността на алгоритъма
      • Сложността на алгоритъма
  • Триангулирана графики като пресечни графики
    • Еволюционните дървета
    • Триангулирана графики като пресечни графики

Лекция #5: Триангулирана графики са перфектни

  • Триангулирана графики са перфектни
    • Доказването този имот
    • Други резултати
  • Изчислителна минималната попълнете
    • Проблемът
    • Напълнете в е NP-Hard
      • Верижни графики
      • Оптимално линеен режим (OLA)
      • Chain графика завършване (CGC)
      • Резултатът за запълване на
    • Проблеми

Лекция #6: Алгоритми за триангулирана графики и съпоставимост графики

  • Някои оптимизация алгоритми за триангулирана графики
    • Изчислителна хроматичната броя и всички максимални клики
    • Намирането $\alpha $ и $k$
  • Съпоставимост графики
    • Някои определения
    • класове Последици
    • Триъгълникът лема
    • Разбиване на графиките

Лекция #7: Уникално частично регулиране графики

  • Уникално частично регулиране графики
  • Характеристиките, и признаване алгоритми

Лекция #8: Някои интересни графиката семейства характеризират с пресичане

  • Въведение
  • пермутация графики
  • $F$ - Графики
  • "Стачка въздушните контрольори"
  • Състав на пермутация диаграма
  • Толерантност графики
  • Интервал графики като подмножество на толерантност графики
  • Обкръжен и неограничени графики толерантност

Лекция #9: Съпоставимост графики

  • Съпоставимост признаване графика
  • Сложността на съпоставимост признаване графика
    • Изпълнение
    • Анализ Сложността
  • Боядисване и други проблеми на съпоставимост графики
    • Съпоставимост графики са перфектни
    • Максимална претеглена клика
    • Изчисляване $\\alpha (G)$
  • Измерението на частични поръчки

Лекция #10: Съпоставимост инварианти и интервала графики

  • Съпоставимост инварианти
  • Интервал графики

Лекция #11: Интервал графики

  • Предпочитание и безразличие
  • Признавайки интервал графики
    • Квадратичен алгоритъм 1
    • Алгоритъм Линеен
  • Повече за пореден 1-е собственост на

Лекция #12: Времеви разсъждение

  • Времеви разсъждение и интервал алгебри
  • Интервал проблеми приложимости
  • Интервал проблеми сандвич и ISAT
  • А линеен алгоритъм време за ISAT ($\\Delta _1}$)
  • Честотна лента, ширина път и правилното ширина път

Индекс

Моля, изпращайте всички отзиви и коментари към: shamir@math.tau.ac.il

Оригинален: http://www.math.tau.ac.il/~rshamir/atga/atga.html