资源描述：
《A Course in Combinatorial Optimization》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ACourseinCombinatorialOptimizationAlexanderSchrijverCWI,Kruislaan413,1098SJAmsterdam,TheNetherlandsandDepartmentofMathematics,UniversityofAmsterdam,PlantageMuidergracht24,1018TVAmsterdam,TheNetherlands.March12,2012copyright°cA.SchrijverContents1.Shortestpathsandtrees51.1.
2、Shortestpathswithnonnegativelengths51.2.SpeedingupDijkstra’salgorithmwithheaps91.3.Shortestpathswitharbitrarylengths121.4.Minimumspanningtrees192.Polytopes,polyhedra,Farkas’lemma,andlinearprogramming232.1.Convexsets232.2.Polytopesandpolyhedra252.3.Farkas’lemma312.4.Linear
3、programming333.Matchingsandcoversinbipartitegraphs393.1.Matchings,covers,andGallai’stheorem393.2.M-augmentingpaths403.3.K˝onig’stheorems413.4.Cardinalitybipartitematchingalgorithm453.5.Weightedbipartitematching473.6.Thematchingpolytope504.Menger’stheorem,flows,andcirculati
4、ons544.1.Menger’stheorem544.2.Flowsinnetworks584.3.Findingamaximumflow604.4.Speedingupthemaximumflowalgorithm654.5.Circulations684.6.Minimum-costflows705.Nonbipartitematching785.1.Tutte’s1-factortheoremandtheTutte-Bergeformula785.2.Cardinalitymatchingalgorithm815.3.Weightedm
5、atchingalgorithm855.4.Thematchingpolytope915.5.TheCunningham-Marshformula956.Problems,algorithms,andrunningtime976.1.Introduction976.2.Words986.3.Problems1006.4.Algorithmsandrunningtime1006.5.TheclassNP1016.6.Theclassco-NP1026.7.NP-completeness1036.8.NP-completenessofthes
6、atisfiabilityproblem1036.9.NP-completenessofsomeotherproblems1066.10.Turingmachines1087.Cliques,stablesets,andcolourings1117.1.Introduction1117.2.Edge-colouringsofbipartitegraphs1157.3.Partiallyorderedsets1217.4.Perfectgraphs1247.5.Chordalgraphs1288.Integerlinearprogrammin
7、gandtotallyunimodularmatrices1328.1.Integerlinearprogramming1328.2.Totallyunimodularmatrices1348.3.Totallyunimodularmatricesfrombipartitegraphs1398.4.Totallyunimodularmatricesfromdirectedgraphs1439.Multicommodityflowsanddisjointpaths1489.1.Introduction1489.2.Twocommodities
8、1539.3.Disjointpathsinacyclicdirectedgraphs1579.4.Vertex-disjointpathsinplanargraphs1599.5.Edge-
