000 03902nam a22005175i 4500
001 978-3-642-03822-8
003 DE-He213
005 20140220084526.0
007 cr nn 008mamaa
008 100318s2010 gw | s |||| 0|eng d
020 _a9783642038228
_9978-3-642-03822-8
024 7 _a10.1007/978-3-642-03822-8
_2doi
050 4 _aQA164-167.2
072 7 _aPBV
_2bicssc
072 7 _aMAT036000
_2bisacsh
082 0 4 _a511.6
_223
100 1 _aHochstättler, Winfried.
_eauthor.
245 1 0 _aCATBox
_h[electronic resource] :
_bAn Interactive Course in Combinatorial Optimization /
_cby Winfried Hochstättler, Alexander Schliep.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c2010.
300 _aXII, 190p. 36 illus.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
505 0 _aDiscrete Problems from Applications -- Basics, Notation and Data Structures -- Minimum Spanning Trees -- Linear Programming Duality -- Shortest Paths -- Maximal Flows -- Minimum-Cost Flows -- Matching -- Weighted Matching.
520 _aGraph algorithms are easy to visualize and indeed there already exists a variety of packages and programs to animate the dynamics when solving problems from graph theory. Still, and somewhat surprisingly, it can be difficult to understand the ideas behind the algorithm from the dynamic display alone. CATBox consists of a software system for animating graph algorithms and a course book which we developed simultaneously. The software system presents both the algorithm and the graph and puts the user always in control of the actual code that is executed. He or she can set breakpoints, proceed in single steps and trace into subroutines. The graph, and additional auxiliary graphs like residual networks, are displayed and provide visual feedback. The course book, intended for readers at advanced undergraduate or graduate level, introduces the ideas and discusses the mathematical background necessary for understanding and verifying the correctness of the algorithms and their complexity. Computer exercises and examples replace the usual static pictures of algorithm dynamics. For this volume we have chosen solely algorithms for classical problems from combinatorial optimization, such as minimum spanning trees, shortest paths, maximum flows, minimum cost flows as well as weighted and unweighted matchings both for bipartite and non-bipartite graphs. We consider non-bipartite weighted matching, in particular in the geometrical case, a highlight of combinatorial optimization. In order to enable the reader to fully enjoy the beauty of the primal-dual solution algorithm for weighted matching, we present all mathematical material not only from the point of view of graph theory, but also with an emphasis on linear programming and its duality. This yields insightful and aesthetically pleasing pictures for matchings, but also for minimum spanning trees. You can find more information at http://schliep.org/CATBox/.
650 0 _aMathematics.
650 0 _aComputational complexity.
650 0 _aCombinatorics.
650 0 _aMathematical optimization.
650 0 _aOperations research.
650 0 _aEconomics, Mathematical.
650 1 4 _aMathematics.
650 2 4 _aCombinatorics.
650 2 4 _aOptimization.
650 2 4 _aOperations Research, Mathematical Programming.
650 2 4 _aDiscrete Mathematics in Computer Science.
650 2 4 _aGame Theory/Mathematical Methods.
700 1 _aSchliep, Alexander.
_eauthor.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer eBooks
776 0 8 _iPrinted edition:
_z9783540148876
856 4 0 _uhttp://dx.doi.org/10.1007/978-3-642-03822-8
912 _aZDB-2-SMA
999 _c111544
_d111544