Graph Theoretic Algorithms

《Graph Theoretic Algorithms》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、iCS762:Graph-theoreticalgorithmsLecturenotesofagraduatecourseUniversityofWaterlooFall1999,Winter2002,Winter2004VersionofSeptember20,2005iiContents1Introduction31.1Somegraphclasses................................31.2Typicalquestions.................................5IInt

2、ervalGraphsAndFriends72Intervalgraphs92.1Astandardizedrepresentation..........................102.2Perfecteliminationorder.............................123PerfectEliminationOrders153.1Algorithmsforgraphswithap.e.o........................153.1.1Colouring.................

3、................153.1.2Clique...................................163.1.3IndependentSet..............................163.2Chordalgraphs..................................173.2.1Separators.................................173.2.2Simplicialvertices...........................

4、..183.2.3Chordalgraphsandsimplicialvertices.................193.3Findingaperfecteliminationorder.......................203.3.1MaximumCardinalitySearch......................203.3.2LexicographicBFS............................213.3.3Testingaperfecteliminationorder........

5、...........254Comparabilitygraphs274.1Complementsofintervalgraphs.........................274.2Relationshiptoothergraphclasses.......................284.3Comparabilitygraphrecognition.........................294.4Problemsoncomparabilitygraphs........................294

6、.4.1CliqueandColouring...........................304.4.2IndependentSet..............................31iiiivCONTENTS5IntervalGraphRecognition335.1Intervalgraphs,chordalgraphs,comparabilitygraphs.............335.2IntervalgraphsandMaximalCliques......................335.2

7、.1FindingMaximalCliques.........................355.2.2PQ-trees..................................365.2.3RecognizingintervalgraphswithPQ-trees...............385.3Otheralgorithmsforrecognizingintervalgraphs................386FriendsofIntervalGraphs396.1Perfectgraphs.....

8、..............................396.2IntersectionGraphs................................406.2.1ChordalGraphs............