Avancerade Ämnen i Grafen Algoritmer

link: http://www.cs.tau.ac.il/~rshamir/atga/atga.html

Detta arkiv innehåller material om kursen „Avancerat Ämnen i Grafen Algoritmer“ © som lärs ut av Ron Shamir , institutionen för datavetenskap, Tel-Aviv universitetet, om 10/91-2/92 (Hösten 92), 4-6/94 (Våren 94) och 4-6/97 (Våren 97). Detta var en termin examen naturligtvis även öppen för seniorer, med ett tre timmars möte varje vecka.

Kursen betonas algoritmiska och strukturella aspekter av „fin“ graph familjer, i synnerhet perfekt grafer, intervall grafer, chordal grafer och poster grafer.
Hösten 92 kursen var till stor del baserad på den klassiska boken av Martin C. Golumbic „Algoritmiska grafteori och Perfekt Grafer‘ (Academic Press, 1980), och i vissa delar också på manuskriptet „The Art of Kombinatorik“, genom att Douglas B. West.
Våren 94 och Våren 97 kursen hade ett liknande sätt, men betonade nyare material, och gjorde en hel del referens till tillämpningar inom molekylär biologi. (Se hemsidan Algoritmer för Molekylärbiologi för mycket mer på dessa aspekter.)

Material tillgängligt:

  • Skribenterna av våren 94 föreläsningar
    Tal blev skriven av eleverna och reviderades av föreläsaren. Den kompletta uppsättningen anteckningar har sedan redigerats och formaterats av Sariel Har-Peled . Tack Sariel!Du kan antingen ladda ner fullständiga anteckningar som en enda postscript-fil (150 sidor), eller varje föreläsning separat.

    Omslag

    • Omslag
    • Innehållsförteckning
    • Lista över figurer

    Föreläsning # 1: Introduktion till grafteori

    • Grundläggande definitioner och noteringar
    • Granskning av grafer
    • Cirkelbågsgrafer
    • Intervallgrafer
    • Linjediagram på bifogade grafer

    Föreläsning # 2: Perfekt Grafer

    • Definition av perfekt graf
    • Några definitioner och egenskaper
    • Perfekt grafteori

    Föreläsning # 3: Perfekta och triangulerade grafer

    • Perfekta grafer
      • $ p $ -Critical Grafer
      • En polyhedral karaktärisering av perfekta grafer
      • Den starka perfekta grafbegreppet
    • Triangulerade grafer
      • Introduktion
      • Karaktäriserande triangulerade grafer
      • Erkänna Triangulerade Grafer
      • Tidskomplexitet

    Föreläsning # 4: Erkännande Triangulerade Grafer

    • Erkänna Triangulerade Grafer
      • Generera en PEO
      • Test av ett elimineringsschema
        • Naivalgoritmen
        • Effektiv algoritm
        • Exempel
        • Algoritmens korrekthet
        • Algoritmens komplexitet
    • Triangulerade grafer som gränsöverskridande grafer
      • Evolutionära träd
      • Triangulerade grafer som gränsöverskridande grafer

    Föreläsning # 5: Triangulerade grafer är perfekta

    • Triangulerade grafer är perfekta
      • Bevisar denna egendom
      • Andra resultat
    • Computing Minimum Fill In
      • Problemet
      • Fyll i är NP-Hard
        • Kedjegrafik
        • Optimal linjär arrangemang (OLA)
        • Kedjegrafikavslutning (CGC)
        • Resultatet för Fyll i
      • problem

    Föreläsning # 6: Algoritmer för triangulerade grafer och jämförbarhetsgrafer

    • Några optimeringsalgoritmer på triangulerade grafer
      • Beräknar det kromatiska talet och alla maximala klick
      • Hitta $ \ alpha $ och $ k $
    • Jämförbarhetsgrafer
      • Några definitioner
      • Implikationsklasser
      • Triangeln Lemma
      • Nedbrytning av grafer

    Föreläsning # 7: Unikt delvis beställbara grafer

    • Unikt delvis beställbara grafer
    • Karakteriseringar och erkännandealgoritmer

    Föreläsning # 8: Några intressanta graffamiljer som kännetecknas av korsningen

    • Introduktion
    • Permutationsgrafer
    • $ F $ -Graphs
    • „Air controllers strejk “
    • En komposition av permutationsschema.
    • Toleransgrafer
    • Intervallgrafer som en delmängd av toleransgrafer.
    • Gränsade och obegränsade toleransgrafer.

    Föreläsning # 9: Jämförbarhetsgrafer

    • Komparabilitetsgrafikigenkänning
    • Komplexiteten av jämförbarhetsgrafikigenkänning
      • Genomförande
      • Komplexitetsanalys
    • Färg och andra problem på jämförbarhetsgrafer
      • Jämförbarhetsgraferna är perfekta
      • Maxviktad klick
      • Beräknar $ \ alpha (G) $
    • Partiell ordningens dimension

    Föreläsning # 10: Jämförbara invarianter och intervallgrafer

    • Jämförbarhetsvariabler
    • Intervallgrafer

    Föreläsning # 11: Intervallgrafer

    • Preference och likgiltighet
    • Erkänna intervallgrafer
      • En kvadratisk algoritm 1
      • En linjär algoritm
    • Mer om den efterföljande 1: s egendom

    Föreläsning # 12: Temporal Reasoning

    • Temporala Reasoning and Interval algebras
    • Intervall satisfiabilitetsproblem
    • Intervall smörgåsproblem och ISAT
    • En linjär tidsalgoritm för ISAT ($ \ Delta _1} $)
    • Bandbredd, banbredd och korrekt banbredd