Course: Advanced Topics in Graph Algorithms Fall 1991/2
-------------------------------------------------------

Oct 16	1	basic graph concepts
		intersection graphs
		interval graphs sneak preview	(Gloumbic Ch. 1)
Oct 23  2	basic algorithmic concepts and ata structures
		BFS, DFS
		Transitive tournaments and topological sorting
						(Golumbic Ch. 2)
Oct 30  3	The Perfect Graph Theorem	(Golumbic Ch 3.2)
Nov  6	4	Trigangulated Graphs: 
			*Fulkerson-Gross, Dirac Thms.
			*perfect elim. order algorithm: Lex BFS validity
						(Golumbic Ch. 4.1-3)
Nov 13	5	Trigangulated Graphs: 
			*Lex BFS complexity
			*Alg to verify a given elim order is perfect
			*Triangulated graphs as intersection graphs
				(Walter-Gavril theorem except 1=>3)
						(Golumbic Ch. 4.3-5)

Nov 20	6	Trigangulated Graphs: 
			*Triangulated graphs as intersection graphs
				(Walter-Gavril theorem 1=>3)
						(Golumbic Ch. 4.5)
			*Minimum Fill In is NP-complete
						(Yannakakis) 
			*Triangulated graphs are perfect
						(Golumbic Ch. 4.6)

Nov 27	7	Trigangulated Graphs: 
			*Algs for comuting chromatic and stability 
				numbers on triangulated graphs
						(Golumbic Ch. 4.7)
         	Comparability Graphs: 
			* implication classes and Gamma-chains
						(Golumbic Ch. 5.1)

Dec 04	8	Comparability Graphs: 
			* Uniquely Partially Orderable graphs
						(Golumbic Ch. 5.2)
			* G-decomposition and characterizations 
					(first part of Golumbic Ch. 5.4)

Dec 11	9	Guest lecture: Marty

Dec 18	10	Comparability Graphs: 
			* Characterization Theorem
			* Recognition algorithm and complexity
			* perfectness and Dilworth theorem.
			* Algorithm for max weighted clique 
			* partial order dimension
						(Golumbic Ch. 5.4-7)

Dec 25	11	Interval Graphs: 
			* Gilmore-Hoffman Characterization Thm
						(Golumbic Ch. 8.2)
			* Lekkerkerekr-Boland Characterization Thm
						(Fishburn CH. 3.4)


Jan  1  12	Temporal Reasoning:
			* Allen's model, ISAT, MLP, ACSP.
			* Interval sandwich is NP-complete.
			* polynomial algorithm for A3-<>.
						(Golumibc-Shamir 90)

Jan  8  13	Interval Graphs: 
			* consecutive and circular ones
			 	recognition, PQ trees (no proofs)
			* Preference and Indifference: semiorder,
				Roberts' theorem
						(Golumbic Ch. 8.3,5)
			* split graphs (survey)
						(Golumbic Ch. 6)

Jan 16  14	brief reviews:
			* Circular arc Graphs
						(Golumbic Ch. 8.6)
			* permutation graphs
						(Golumbic Ch. 7)
			* perfect elimination bipartite graphs
			* chordal bipartite graphs.
						(Golumbic Ch. 11)
			* Greedily solvable network flow problems
					(Adler-Hoffman-Shamir 90)