Changes in doc/groups.dox [789:8e68671af789:818:8452ca46e29a] in lemon
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r789 r818 317 317 318 318 This group contains the common graph search algorithms, namely 319 \e breadthfirst \e search (BFS) and \e depthfirst \e search (DFS). 319 \e breadthfirst \e search (BFS) and \e depthfirst \e search (DFS) 320 \ref clrs01algorithms. 320 321 */ 321 322 … … 325 326 \brief Algorithms for finding shortest paths. 326 327 327 This group contains the algorithms for finding shortest paths in digraphs. 328 This group contains the algorithms for finding shortest paths in digraphs 329 \ref clrs01algorithms. 328 330 329 331  \ref Dijkstra algorithm for finding shortest paths from a source node … … 347 349 348 350 This group contains the algorithms for finding minimum cost spanning 349 trees and arborescences .351 trees and arborescences \ref clrs01algorithms. 350 352 */ 351 353 … … 356 358 357 359 This group contains the algorithms for finding maximum flows and 358 feasible circulations .360 feasible circulations \ref clrs01algorithms, \ref amo93networkflows. 359 361 360 362 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 371 373 372 374 LEMON contains several algorithms for solving maximum flow problems: 373  \ref EdmondsKarp EdmondsKarp algorithm. 374  \ref Preflow GoldbergTarjan's preflow pushrelabel algorithm. 375  \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 376  \ref GoldbergTarjan Preflow pushrelabel algorithm with dynamic trees. 377 378 In most cases the \ref Preflow "Preflow" algorithm provides the 375  \ref EdmondsKarp EdmondsKarp algorithm 376 \ref edmondskarp72theoretical. 377  \ref Preflow GoldbergTarjan's preflow pushrelabel algorithm 378 \ref goldberg88newapproach. 379  \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 380 \ref dinic70algorithm, \ref sleator83dynamic. 381  \ref GoldbergTarjan !Preflow pushrelabel algorithm with dynamic trees 382 \ref goldberg88newapproach, \ref sleator83dynamic. 383 384 In most cases the \ref Preflow algorithm provides the 379 385 fastest method for computing a maximum flow. All implementations 380 386 also provide functions to query the minimum cut, which is the dual … … 394 400 395 401 This group contains the algorithms for finding minimum cost flows and 396 circulations. For more information about this problem and its dual 397 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 402 circulations \ref amo93networkflows. For more information about this 403 problem and its dual solution, see \ref min_cost_flow 404 "Minimum Cost Flow Problem". 398 405 399 406 LEMON contains several algorithms for this problem. 400 407  \ref NetworkSimplex Primal Network Simplex algorithm with various 401 pivot strategies .408 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. 402 409  \ref CostScaling PushRelabel and AugmentRelabel algorithms based on 403 cost scaling. 410 cost scaling \ref goldberg90approximation, \ref goldberg97efficient, 411 \ref bunnagel98efficient. 404 412  \ref CapacityScaling Successive Shortest %Path algorithm with optional 405 capacity scaling. 406  \ref CancelAndTighten The Cancel and Tighten algorithm. 407  \ref CycleCanceling CycleCanceling algorithms. 413 capacity scaling \ref edmondskarp72theoretical. 414  \ref CancelAndTighten The Cancel and Tighten algorithm 415 \ref goldberg89cyclecanceling. 416  \ref CycleCanceling CycleCanceling algorithms 417 \ref klein67primal, \ref goldberg89cyclecanceling. 408 418 409 419 In general NetworkSimplex is the most efficient implementation, … … 441 451 If you want to find minimum cut just between two distinict nodes, 442 452 see the \ref max_flow "maximum flow problem". 453 */ 454 455 /** 456 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms 457 @ingroup algs 458 \brief Algorithms for finding minimum mean cycles. 459 460 This group contains the algorithms for finding minimum mean cycles 461 \ref clrs01algorithms, \ref amo93networkflows. 462 463 The \e minimum \e mean \e cycle \e problem is to find a directed cycle 464 of minimum mean length (cost) in a digraph. 465 The mean length of a cycle is the average length of its arcs, i.e. the 466 ratio between the total length of the cycle and the number of arcs on it. 467 468 This problem has an important connection to \e conservative \e length 469 \e functions, too. A length function on the arcs of a digraph is called 470 conservative if and only if there is no directed cycle of negative total 471 length. For an arbitrary length function, the negative of the minimum 472 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the 473 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length 474 function. 475 476 LEMON contains three algorithms for solving the minimum mean cycle problem: 477  \ref Karp "Karp"'s original algorithm \ref amo93networkflows, 478 \ref dasdan98minmeancycle. 479  \ref HartmannOrlin "HartmannOrlin"'s algorithm, which is an improved 480 version of Karp's algorithm \ref dasdan98minmeancycle. 481  \ref Howard "Howard"'s policy iteration algorithm 482 \ref dasdan98minmeancycle. 483 484 In practice, the Howard algorithm proved to be by far the most efficient 485 one, though the best known theoretical bound on its running time is 486 exponential. 487 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space 488 O(n<sup>2</sup>+e), but the latter one is typically faster due to the 489 applied early termination scheme. 443 490 */ 444 491 … … 535 582 536 583 /** 537 @defgroup lp_group L p and MipSolvers584 @defgroup lp_group LP and MIP Solvers 538 585 @ingroup gen_opt_group 539 \brief Lp and Mip solver interfaces for LEMON. 540 541 This group contains Lp and Mip solver interfaces for LEMON. The 542 various LP solvers could be used in the same manner with this 543 interface. 586 \brief LP and MIP solver interfaces for LEMON. 587 588 This group contains LP and MIP solver interfaces for LEMON. 589 Various LP solvers could be used in the same manner with this 590 highlevel interface. 591 592 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 593 \ref cplex, \ref soplex. 544 594 */ 545 595
Note: See TracChangeset
for help on using the changeset viewer.