LEADER 03135nam 2200457 450 001 996546840903316 005 20230730235921.0 010 $a9789811999529$b(electronic bk.) 010 $z9789811999512 024 7 $a10.1007/978-981-19-9952-9 035 $a(MiAaPQ)EBC7220723 035 $a(Au-PeEL)EBL7220723 035 $a(OCoLC)1374428713 035 $a(DE-He213)978-981-19-9952-9 035 $a(PPN)269100466 035 $a(EXLCZ)9926347416400041 100 $a20230730d2023 uy 0 101 0 $aeng 135 $aurcnu|||||||| 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 10$aPedigree polytopes $enew insights on computational complexity of combinatorial optimization problems /$fTirukkattuppalli Subramanyam Arthanari 205 $a1st ed. 2023. 210 1$aSingapore :$cSpringer,$d[2023] 210 4$dİ2023 215 $a1 online resource (235 pages) 311 08$aPrint version: Arthanari, Tirukkattuppalli Subramanyam Pedigree Polytopes Singapore : Springer,c2023 9789811999512 320 $aIncludes bibliographical references and index. 327 $aChapter 1: Prologue -- Chapter 2: Notations, Definitions and Briefs -- Chapter 3: Motivation for Studying Pedigrees -- Chapter 4: Structure of the Pedigree Polytope -- Chapter 5: Membership Checking in Pedigree Polytopes -- Chapter 6: Computational Complexity of Membership Checking -- Chapter 7: Efficient Checking of Membership in Pedigree Polytope and its Implications -- Chapter 8: Epilogue. 330 $aThis book defines and studies a combinatorial object called the pedigree and develops the theory for optimising a linear function over the convex hull of pedigrees (the Pedigree polytope). A strongly polynomial algorithm implementing the framework given in the book for checking membership in the pedigree polytope is a major contribution. This book challenges the popularly held belief in computer science that a problem included in the NP-complete class may not have a polynomial algorithm to solve. By showing STSP has a polynomial algorithm, this book settles the P vs NP question. This book has illustrative examples, figures, and easily accessible proofs for showing this unexpected result. This book introduces novel constructions and ideas previously not used in the literature. Another interesting feature of this book is it uses basic max-flow and linear multicommodity flow algorithms and concepts in these proofs establishing efficient membership checking for the pedigree polytope. Chapters 3-7 can be adopted to give a course on Efficient Combinatorial Optimization. This book is the culmination of the author's research that started in 1982 through a presentation on a new formulation of STSP at the XIth International Symposium on Mathematical Programming at Bonn. 606 $aPolytopes 615 0$aPolytopes. 676 $a895.134 700 $aArthanari$b Tirukkattuppalli Subramanyam$01349112 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 912 $a996546840903316 996 $aPedigree Polytopes$93087046 997 $aUNISA