Changeset 963:3ed8f7c8bed8 in lemon
 Timestamp:
 03/18/10 14:50:32 (10 years ago)
 Branch:
 1.2
 Parents:
 961:7af2ae7c1428 (diff), 962:87569cb5734d (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Tags:
 r1.2
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r961 r963 264 264 265 265 /** 266 @defgroup matrices Matrices267 @ingroup datas268 \brief Two dimensional data storages implemented in LEMON.269 270 This group contains two dimensional data storages implemented in LEMON.271 */272 273 /**274 266 @defgroup auxdat Auxiliary Data Structures 275 267 @ingroup datas … … 449 441 450 442 LEMON contains three algorithms for solving the minimum mean cycle problem: 451  \ref Karp "Karp"'s original algorithm \ref amo93networkflows,443  \ref KarpMmc Karp's original algorithm \ref amo93networkflows, 452 444 \ref dasdan98minmeancycle. 453  \ref HartmannOrlin "HartmannOrlin"'s algorithm, which is an improved445  \ref HartmannOrlinMmc HartmannOrlin's algorithm, which is an improved 454 446 version of Karp's algorithm \ref dasdan98minmeancycle. 455  \ref Howard "Howard"'s policy iteration algorithm447  \ref HowardMmc Howard's policy iteration algorithm 456 448 \ref dasdan98minmeancycle. 457 449 458 In practice, the Howard algorithm proved to be by far the most efficient459 one, though the best known theoretical bound on its running time is 460 exponential.461 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space462 O(n<sup>2</sup>+e), but the latter one is typically faster due to the 463 applied early termination scheme.450 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the 451 most efficient one, though the best known theoretical bound on its running 452 time is exponential. 453 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "HartmannOrlin" algorithms 454 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is 455 typically faster due to the applied early termination scheme. 464 456 */ 465 457 
doc/groups.dox
r959 r963 287 287 288 288 /** 289 @defgroup matrices Matrices290 @ingroup auxdat291 \brief Two dimensional data storages implemented in LEMON.292 293 This group contains two dimensional data storages implemented in LEMON.294 */295 296 /**297 289 @defgroup algs Algorithms 298 290 \brief This group contains the several algorithms … … 327 319 but the digraph should not contain directed cycles with negative total 328 320 length. 329  \ref FloydWarshall "FloydWarshall" and \ref Johnson "Johnson" algorithms330 for solving the \e allpairs \e shortest \e paths \e problem when arc331 lenghts can be either positive or negative, but the digraph should332 not contain directed cycles with negative total length.333 321  \ref Suurballe A successive shortest path algorithm for finding 334 322 arcdisjoint paths between two nodes having minimum total length. … … 364 352 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 365 353 366 LEMON contains several algorithms for solving maximum flow problems: 367  \ref EdmondsKarp EdmondsKarp algorithm 368 \ref edmondskarp72theoretical. 369  \ref Preflow GoldbergTarjan's preflow pushrelabel algorithm 370 \ref goldberg88newapproach. 371  \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 372 \ref dinic70algorithm, \ref sleator83dynamic. 373  \ref GoldbergTarjan !Preflow pushrelabel algorithm with dynamic trees 374 \ref goldberg88newapproach, \ref sleator83dynamic. 375 376 In most cases the \ref Preflow algorithm provides the 377 fastest method for computing a maximum flow. All implementations 378 also provide functions to query the minimum cut, which is the dual 379 problem of maximum flow. 354 \ref Preflow is an efficient implementation of GoldbergTarjan's 355 preflow pushrelabel algorithm \ref goldberg88newapproach for finding 356 maximum flows. It also provides functions to query the minimum cut, 357 which is the dual problem of maximum flow. 380 358 381 359 \ref Circulation is a preflow pushrelabel algorithm implemented directly … … 434 412  \ref HaoOrlin "HaoOrlin algorithm" for calculating minimum cut 435 413 in directed graphs. 436  \ref NagamochiIbaraki "NagamochiIbaraki algorithm" for437 calculating minimum cut in undirected graphs.438 414  \ref GomoryHu "GomoryHu tree computation" for calculating 439 415 allpairs minimum cut in undirected graphs. … … 498 474 499 475 The matching algorithms implemented in LEMON: 500  \ref MaxBipartiteMatching HopcroftKarp augmenting path algorithm501 for calculating maximum cardinality matching in bipartite graphs.502  \ref PrBipartiteMatching Pushrelabel algorithm503 for calculating maximum cardinality matching in bipartite graphs.504  \ref MaxWeightedBipartiteMatching505 Successive shortest path algorithm for calculating maximum weighted506 matching and maximum weighted bipartite matching in bipartite graphs.507  \ref MinCostMaxBipartiteMatching508 Successive shortest path algorithm for calculating minimum cost maximum509 matching in bipartite graphs.510 476  \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 511 477 maximum cardinality matching in general graphs. … … 552 518 553 519 /** 554 @defgroup approx Approximation Algorithms555 @ingroup algs556 \brief Approximation algorithms.557 558 This group contains the approximation and heuristic algorithms559 implemented in LEMON.560 */561 562 /**563 520 @defgroup auxalg Auxiliary Algorithms 564 521 @ingroup algs … … 589 546 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 590 547 \ref cplex, \ref soplex. 591 */592 593 /**594 @defgroup lp_utils Tools for Lp and Mip Solvers595 @ingroup lp_group596 \brief Helper tools to the Lp and Mip solvers.597 598 This group adds some helper tools to general optimization framework599 implemented in LEMON.600 */601 602 /**603 @defgroup metah Metaheuristics604 @ingroup gen_opt_group605 \brief Metaheuristics for LEMON library.606 607 This group contains some metaheuristic optimization tools.608 548 */ 609 549
Note: See TracChangeset
for help on using the changeset viewer.