Avancerede emner i grafalgoritmer


Fuld kredit går til – http://www.math.tau.ac.il/~rshamir/atga/atga.html


Dette arkiv indeholder materiale om kurset “Advanced Topics in Graph Algorithms” © undervist af Ron Shamir i afdelingen for datalogi ved Tel-Aviv universitet, den 10 / 91-2 / 92 (efterår 92), 4-6 / 94 ( Spring 94) og 4-6 / 97 (Spring 97). Dette var et semesterkursus åbent også for seniorer med et tre timers møde hver uge.

Kurset understregede algoritmiske og strukturelle aspekter af “pæne” graffamilier, især perfekte grafer, intervalgrafer, akkordgrafer og sammenlignelighedsgrafer.

I efteråret 92 var kurset i vid udstrækning baseret på den klassiske bog af Martin C. Golumbic “Algorithmic Graph Theory and Perfect Graphs ‘(Academic Press, 1980) og i nogle dele også på manuskriptet” The Art of Combinatorics “, af Douglas B. West.
Spring 94 og Spring 97-kurset havde et lignende grundlag, men understregede nyere materiale og henviste meget til anvendelser inden for molekylærbiologi. (Se websiden Algoritmer for Molecular Biology for meget mere om disse aspekter.)

Tilgængeligt materiale:

  • Scribes of Spring 94 forelæsninger

Foredrag blev skrevet af de studerende og revideret af underviseren. Det komplette sæt noter blev efterfølgende redigeret og formateret af Sariel Har-Peled. Tak, Sariel!

Du kan enten downloade de komplette noter som en enkelt efterskriftfil (150 sider) eller hver forelæsning separat.

For oversættelser af forelæsningsnotater til andre sprog se her.

  • Dække over
    • Forside
    • Indholdsfortegnelse
    • Liste over figurer

Foredrag #1: Introduktion til grafteori

  • Grundlæggende definitioner og notationer
  • Krydsgrafer
  • Cirkelbue-grafer
  • Intervalgrafer
  • Linjegrafer af topartsgrafer

Foredrag #2: Perfekte grafer

  • Definition af perfekt graf
  • Nogle definitioner og egenskaber
  • Perfekt graf sætning

Foredrag #3: Perfekte og trekantede grafer

  • Perfekte grafer
    • $ p $ -Kritiske grafer
    • En polyhedral karakterisering af perfekte grafer
    • Den stærke perfekte grafkonjektion
  • Trekantede grafer
    • Introduktion
    • Karakterisering af trekantede grafer
    • Genkendelse af trekantede grafer
    • Tidskompleksitet

Foredrag #4: Genkendelse af trekanter

  • Genkendelse af trekantede grafer
    • Generering af en PEO
    • Test af en eliminationsordning
      • Naiv algoritme
      • Effektiv algoritme
      • Eksempel
      • Korrektheden af ​​algoritmen
      • Algoritmens kompleksitet
  • Triangulerede grafer som skæringsgrafer
    • Evolutionære træer
    • Triangulerede grafer som skæringsgrafer

Foredrag #5: Triangulerede grafer er perfekte

  • Trekantede grafer er perfekte
    • Beviser denne ejendom
    • Andre resultater
  • Beregning af minimum udfyldning
    • Problemet
    • Udfyldning er NP-hård
      • Kædegrafer
      • Optimalt lineært arrangement (OLA)
      • Fuldførelse af kædegraf (CGC)
      • Resultatet for Udfyld
    • Problemer

Foredrag #6: Algoritmer til trekantsgrafer og sammenlignelighedsgrafer

  • Nogle optimeringsalgoritmer på trekantede grafer
    • Beregner det kromatiske antal og alle maksimale klik
    • Finder $ \ alpha $ og $ k $
  • Sammenlignelighed Grafer
    • Nogle definitioner
    • Implikationskurser
    • Trekant-lemmaet
    • Nedbrydning af grafer

Foredrag #7: Entydigt delvist bestilbare grafer

  • Unikt delvist bestilbare grafer
  • Karakteriseringer og genkendelsesalgoritmer

Foredrag #8: Nogle interessante graffamilier karakteriseret ved

  • vejkryds
  • Introduktion
  • Permutationsgrafer
  • $ F $ -grafer
  • “ Luftkontrollerne strejker ”
  • En sammensætning af permutationsdiagram.
  • Tolerance grafer
  • Intervalgrafer som en delmængde af tolerancegrafer.
  • Afgrænsede og ubegrænsede tolerancegrafer.

Foredrag #9: Sammenlignelighed Grafer

  • Sammenlignelighed Grafgenkendelse
  • Kompleksiteten af ​​sammenligning af grafgenkendelse
    • Implementering
    • Kompleksitetsanalyse
  • Farvelægning og andre problemer med sammenlignelighedsgrafer
    • Sammenlignelighed Grafer er perfekte
    • Maksimal vægtet klik
    • Beregner $ \ alpha (G) $
  • Dimensionen af ​​delordrer

Foredrag #10: Sammenlignelighed invarianter og intervallgrafer

  • Sammenlignelighed invarianter
  • Intervalgrafer

Foredrag #11: Intervalgrafer

  • Præference og ligegyldighed
  • Genkendelse af intervalgrafer
    • En kvadratisk algoritme 1
    • En lineær algoritme
  • Mere om den på hinanden følgende 1’s ejendom

Foredrag #12: Temporal begrundelse

  • Temporal ræsonnement og intervalalgebraer
  • Intervallers tilfredshedsproblemer
  • Intervallesandwichproblemer og ISAT
  • En lineær tidsalgoritme for ISAT ($ \ Delta _1} $)
  • Båndbredde, sti-bredde og korrekt sti-bredde

Indeks

Send al feedback og kommentarer til: rshamir@tau.ac.il