r918:86613aa28a0c
Thu, 04 Mar 2010 10:17:02
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -111,7 +111,7 @@ |
| 111 | 111 |
/// solution) can be obtained using the query functions. |
| 112 | 112 |
/// |
| 113 | 113 |
/// The primal solution is multiplied by |
| 114 |
/// \ref |
|
| 114 |
/// \ref MaxFractionalMatching::primalScale "2". |
|
| 115 | 115 |
/// |
| 116 | 116 |
/// \tparam GR The undirected graph type the algorithm runs on. |
| 117 | 117 |
#ifdef DOXYGEN |
| ... | ... |
@@ -632,9 +632,8 @@ |
| 632 | 632 |
/// \brief Weighted fractional matching in general graphs |
| 633 | 633 |
/// |
| 634 | 634 |
/// This class provides an efficient implementation of fractional |
| 635 |
/// matching algorithm. The implementation is based on extensive use |
|
| 636 |
/// of priority queues and provides \f$O(nm\log n)\f$ time |
|
| 637 |
/// |
|
| 635 |
/// matching algorithm. The implementation uses priority queues and |
|
| 636 |
/// provides \f$O(nm\log n)\f$ time complexity. |
|
| 638 | 637 |
/// |
| 639 | 638 |
/// The maximum weighted fractional matching is a relaxation of the |
| 640 | 639 |
/// maximum weighted matching problem where the odd set constraints |
| ... | ... |
@@ -653,7 +652,7 @@ |
| 653 | 652 |
/// problem is the following. |
| 654 | 653 |
/// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f]
|
| 655 | 654 |
/// \f[y_u \ge 0 \quad \forall u \in V\f] |
| 656 |
/// \f[\min \sum_{u \in V}y_u \f]
|
|
| 655 |
/// \f[\min \sum_{u \in V}y_u \f]
|
|
| 657 | 656 |
/// |
| 658 | 657 |
/// The algorithm can be executed with the run() function. |
| 659 | 658 |
/// After it the matching (the primal solution) and the dual solution |
| ... | ... |
@@ -661,8 +660,8 @@ |
| 661 | 660 |
/// |
| 662 | 661 |
/// If the value type is integer, then the primal and the dual |
| 663 | 662 |
/// solutions are multiplied by |
| 664 |
/// \ref MaxWeightedMatching::primalScale "2" and |
|
| 665 |
/// \ref MaxWeightedMatching::dualScale "4" respectively. |
|
| 663 |
/// \ref MaxWeightedFractionalMatching::primalScale "2" and |
|
| 664 |
/// \ref MaxWeightedFractionalMatching::dualScale "4" respectively. |
|
| 666 | 665 |
/// |
| 667 | 666 |
/// \tparam GR The undirected graph type the algorithm runs on. |
| 668 | 667 |
/// \tparam WM The type edge weight map. The default type is |
| ... | ... |
@@ -1270,7 +1269,7 @@ |
| 1270 | 1269 |
|
| 1271 | 1270 |
/// \brief Run the algorithm. |
| 1272 | 1271 |
/// |
| 1273 |
/// This method runs the \c % |
|
| 1272 |
/// This method runs the \c %MaxWeightedFractionalMatching algorithm. |
|
| 1274 | 1273 |
/// |
| 1275 | 1274 |
/// \note mwfm.run() is just a shortcut of the following code. |
| 1276 | 1275 |
/// \code |
| ... | ... |
@@ -1400,9 +1399,8 @@ |
| 1400 | 1399 |
/// \brief Weighted fractional perfect matching in general graphs |
| 1401 | 1400 |
/// |
| 1402 | 1401 |
/// This class provides an efficient implementation of fractional |
| 1403 |
/// matching algorithm. The implementation is based on extensive use |
|
| 1404 |
/// of priority queues and provides \f$O(nm\log n)\f$ time |
|
| 1405 |
/// |
|
| 1402 |
/// matching algorithm. The implementation uses priority queues and |
|
| 1403 |
/// provides \f$O(nm\log n)\f$ time complexity. |
|
| 1406 | 1404 |
/// |
| 1407 | 1405 |
/// The maximum weighted fractional perfect matching is a relaxation |
| 1408 | 1406 |
/// of the maximum weighted perfect matching problem where the odd |
| ... | ... |
@@ -1420,7 +1418,7 @@ |
| 1420 | 1418 |
/// used to check the result of the algorithm. The dual linear |
| 1421 | 1419 |
/// problem is the following. |
| 1422 | 1420 |
/// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f]
|
| 1423 |
/// \f[\min \sum_{u \in V}y_u \f]
|
|
| 1421 |
/// \f[\min \sum_{u \in V}y_u \f]
|
|
| 1424 | 1422 |
/// |
| 1425 | 1423 |
/// The algorithm can be executed with the run() function. |
| 1426 | 1424 |
/// After it the matching (the primal solution) and the dual solution |
| ... | ... |
@@ -1428,8 +1426,8 @@ |
| 1428 | 1426 |
|
| 1429 | 1427 |
/// If the value type is integer, then the primal and the dual |
| 1430 | 1428 |
/// solutions are multiplied by |
| 1431 |
/// \ref MaxWeightedMatching::primalScale "2" and |
|
| 1432 |
/// \ref MaxWeightedMatching::dualScale "4" respectively. |
|
| 1429 |
/// \ref MaxWeightedPerfectFractionalMatching::primalScale "2" and |
|
| 1430 |
/// \ref MaxWeightedPerfectFractionalMatching::dualScale "4" respectively. |
|
| 1433 | 1431 |
/// |
| 1434 | 1432 |
/// \tparam GR The undirected graph type the algorithm runs on. |
| 1435 | 1433 |
/// \tparam WM The type edge weight map. The default type is |
| ... | ... |
@@ -2005,7 +2003,8 @@ |
| 2005 | 2003 |
|
| 2006 | 2004 |
/// \brief Run the algorithm. |
| 2007 | 2005 |
/// |
| 2008 |
/// This method runs the \c % |
|
| 2006 |
/// This method runs the \c %MaxWeightedPerfectFractionalMatching |
|
| 2007 |
/// algorithm. |
|
| 2009 | 2008 |
/// |
| 2010 | 2009 |
/// \note mwfm.run() is just a shortcut of the following code. |
| 2011 | 2010 |
/// \code |
0 comments (0 inline)