doc/references.bib
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:26:13 +0100
changeset 806 fa6f37d7a25b
parent 754 2de0fc630899
child 904 c279b19abc62
permissions -rw-r--r--
Entirely rework CapacityScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster (up to 2-5 times faster on large graphs).
- Handle GEQ supply type (LEQ is not supported).
- Handle negative costs for arcs of finite capacity.
(Note that this algorithm cannot handle arcs of negative cost
and infinite upper bound, thus it returns UNBOUNDED if such
an arc exists.)
- Extend the documentation.
kpeter@743
     1
%%%%% Defining LEMON %%%%%
kpeter@743
     2
kpeter@743
     3
@misc{lemon,
kpeter@743
     4
  key =          {LEMON},
kpeter@743
     5
  title =        {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and
kpeter@743
     6
                  {O}ptimization in {N}etworks},
kpeter@743
     7
  howpublished = {\url{http://lemon.cs.elte.hu/}},
kpeter@743
     8
  year =         2009
kpeter@743
     9
}
kpeter@743
    10
kpeter@743
    11
@misc{egres,
kpeter@743
    12
  key =          {EGRES},
kpeter@743
    13
  title =        {{EGRES} -- {E}gerv{\'a}ry {R}esearch {G}roup on
kpeter@743
    14
                  {C}ombinatorial {O}ptimization},
kpeter@754
    15
  url =          {http://www.cs.elte.hu/egres/}
kpeter@743
    16
}
kpeter@743
    17
kpeter@743
    18
@misc{coinor,
kpeter@743
    19
  key =          {COIN-OR},
kpeter@743
    20
  title =        {{COIN-OR} -- {C}omputational {I}nfrastructure for
kpeter@743
    21
                  {O}perations {R}esearch},
kpeter@754
    22
  url =          {http://www.coin-or.org/}
kpeter@743
    23
}
kpeter@743
    24
kpeter@743
    25
kpeter@743
    26
%%%%% Other libraries %%%%%%
kpeter@743
    27
kpeter@743
    28
@misc{boost,
kpeter@743
    29
  key =          {Boost},
kpeter@743
    30
  title =        {{B}oost {C++} {L}ibraries},
kpeter@754
    31
  url =          {http://www.boost.org/}
kpeter@743
    32
}
kpeter@743
    33
kpeter@743
    34
@book{bglbook,
kpeter@743
    35
  author =       {Jeremy G. Siek and Lee-Quan Lee and Andrew
kpeter@743
    36
                  Lumsdaine},
kpeter@743
    37
  title =        {The Boost Graph Library: User Guide and Reference
kpeter@743
    38
                  Manual},
kpeter@743
    39
  publisher =    {Addison-Wesley},
kpeter@743
    40
  year =         2002
kpeter@743
    41
}
kpeter@743
    42
kpeter@743
    43
@misc{leda,
kpeter@743
    44
  key =          {LEDA},
kpeter@743
    45
  title =        {{LEDA} -- {L}ibrary of {E}fficient {D}ata {T}ypes and
kpeter@743
    46
                  {A}lgorithms},
kpeter@754
    47
  url =          {http://www.algorithmic-solutions.com/}
kpeter@743
    48
}
kpeter@743
    49
kpeter@743
    50
@book{ledabook,
kpeter@743
    51
  author =       {Kurt Mehlhorn and Stefan N{\"a}her},
kpeter@743
    52
  title =        {{LEDA}: {A} platform for combinatorial and geometric
kpeter@743
    53
                  computing},
kpeter@743
    54
  isbn =         {0-521-56329-1},
kpeter@743
    55
  publisher =    {Cambridge University Press},
kpeter@743
    56
  address =      {New York, NY, USA},
kpeter@743
    57
  year =         1999
kpeter@743
    58
}
kpeter@743
    59
kpeter@743
    60
kpeter@743
    61
%%%%% Tools that LEMON depends on %%%%%
kpeter@743
    62
kpeter@743
    63
@misc{cmake,
kpeter@743
    64
  key =          {CMake},
kpeter@743
    65
  title =        {{CMake} -- {C}ross {P}latform {M}ake},
kpeter@754
    66
  url =          {http://www.cmake.org/}
kpeter@743
    67
}
kpeter@743
    68
kpeter@743
    69
@misc{doxygen,
kpeter@743
    70
  key =          {Doxygen},
kpeter@743
    71
  title =        {{Doxygen} -- {S}ource code documentation generator
kpeter@743
    72
                  tool},
kpeter@754
    73
  url =          {http://www.doxygen.org/}
kpeter@743
    74
}
kpeter@743
    75
kpeter@743
    76
kpeter@743
    77
%%%%% LP/MIP libraries %%%%%
kpeter@743
    78
kpeter@743
    79
@misc{glpk,
kpeter@743
    80
  key =          {GLPK},
kpeter@743
    81
  title =        {{GLPK} -- {GNU} {L}inear {P}rogramming {K}it},
kpeter@754
    82
  url =          {http://www.gnu.org/software/glpk/}
kpeter@743
    83
}
kpeter@743
    84
kpeter@743
    85
@misc{clp,
kpeter@743
    86
  key =          {Clp},
kpeter@743
    87
  title =        {{Clp} -- {Coin-Or} {L}inear {P}rogramming},
kpeter@754
    88
  url =          {http://projects.coin-or.org/Clp/}
kpeter@743
    89
}
kpeter@743
    90
kpeter@743
    91
@misc{cbc,
kpeter@743
    92
  key =          {Cbc},
kpeter@743
    93
  title =        {{Cbc} -- {Coin-Or} {B}ranch and {C}ut},
kpeter@754
    94
  url =          {http://projects.coin-or.org/Cbc/}
kpeter@743
    95
}
kpeter@743
    96
kpeter@743
    97
@misc{cplex,
kpeter@743
    98
  key =          {CPLEX},
kpeter@743
    99
  title =        {{ILOG} {CPLEX}},
kpeter@754
   100
  url =          {http://www.ilog.com/}
kpeter@743
   101
}
kpeter@743
   102
kpeter@743
   103
@misc{soplex,
kpeter@743
   104
  key =          {SoPlex},
kpeter@743
   105
  title =        {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented
kpeter@743
   106
                  {S}implex},
kpeter@754
   107
  url =          {http://soplex.zib.de/}
kpeter@743
   108
}
kpeter@743
   109
kpeter@743
   110
kpeter@743
   111
%%%%% General books %%%%%
kpeter@743
   112
kpeter@743
   113
@book{amo93networkflows,
kpeter@743
   114
  author =       {Ravindra K. Ahuja and Thomas L. Magnanti and James
kpeter@743
   115
                  B. Orlin},
kpeter@743
   116
  title =        {Network Flows: Theory, Algorithms, and Applications},
kpeter@743
   117
  publisher =    {Prentice-Hall, Inc.},
kpeter@743
   118
  year =         1993,
kpeter@743
   119
  month =        feb,
kpeter@743
   120
  isbn =         {978-0136175490}
kpeter@743
   121
}
kpeter@743
   122
kpeter@743
   123
@book{schrijver03combinatorial,
kpeter@743
   124
  author =       {Alexander Schrijver},
kpeter@743
   125
  title =        {Combinatorial Optimization: Polyhedra and Efficiency},
kpeter@743
   126
  publisher =    {Springer-Verlag},
kpeter@743
   127
  year =         2003,
kpeter@743
   128
  isbn =         {978-3540443896}
kpeter@743
   129
}
kpeter@743
   130
kpeter@743
   131
@book{clrs01algorithms,
kpeter@743
   132
  author =       {Thomas H. Cormen and Charles E. Leiserson and Ronald
kpeter@743
   133
                  L. Rivest and Clifford Stein},
kpeter@743
   134
  title =        {Introduction to Algorithms},
kpeter@743
   135
  publisher =    {The MIT Press},
kpeter@743
   136
  year =         2001,
kpeter@743
   137
  edition =      {2nd}
kpeter@743
   138
}
kpeter@743
   139
kpeter@743
   140
@book{stroustrup00cpp,
kpeter@743
   141
  author =       {Bjarne Stroustrup},
kpeter@743
   142
  title =        {The C++ Programming Language},
kpeter@743
   143
  edition =      {3rd},
kpeter@743
   144
  publisher =    {Addison-Wesley Professional},
kpeter@743
   145
  isbn =         0201700735,
kpeter@743
   146
  month =        {February},
kpeter@743
   147
  year =         2000
kpeter@743
   148
}
kpeter@743
   149
kpeter@743
   150
kpeter@743
   151
%%%%% Maximum flow algorithms %%%%%
kpeter@743
   152
kpeter@755
   153
@article{edmondskarp72theoretical,
kpeter@755
   154
  author =       {Jack Edmonds and Richard M. Karp},
kpeter@755
   155
  title =        {Theoretical improvements in algorithmic efficiency
kpeter@755
   156
                  for network flow problems},
kpeter@755
   157
  journal =      {Journal of the ACM},
kpeter@755
   158
  year =         1972,
kpeter@755
   159
  volume =       19,
kpeter@755
   160
  number =       2,
kpeter@755
   161
  pages =        {248-264}
kpeter@755
   162
}
kpeter@755
   163
kpeter@755
   164
@article{goldberg88newapproach,
kpeter@743
   165
  author =       {Andrew V. Goldberg and Robert E. Tarjan},
kpeter@743
   166
  title =        {A new approach to the maximum flow problem},
kpeter@755
   167
  journal =      {Journal of the ACM},
kpeter@755
   168
  year =         1988,
kpeter@755
   169
  volume =       35,
kpeter@755
   170
  number =       4,
kpeter@755
   171
  pages =        {921-940}
kpeter@743
   172
}
kpeter@743
   173
kpeter@743
   174
@article{dinic70algorithm,
kpeter@743
   175
  author =       {E. A. Dinic},
kpeter@743
   176
  title =        {Algorithm for solution of a problem of maximum flow
kpeter@743
   177
                  in a network with power estimation},
kpeter@743
   178
  journal =      {Soviet Math. Doklady},
kpeter@743
   179
  year =         1970,
kpeter@743
   180
  volume =       11,
kpeter@743
   181
  pages =        {1277-1280}
kpeter@743
   182
}
kpeter@743
   183
kpeter@743
   184
@article{goldberg08partial,
kpeter@743
   185
  author =       {Andrew V. Goldberg},
kpeter@743
   186
  title =        {The Partial Augment-Relabel Algorithm for the
kpeter@743
   187
                  Maximum Flow Problem},
kpeter@743
   188
  journal =      {16th Annual European Symposium on Algorithms},
kpeter@743
   189
  year =         2008,
kpeter@743
   190
  pages =        {466-477}
kpeter@743
   191
}
kpeter@743
   192
kpeter@743
   193
@article{sleator83dynamic,
kpeter@743
   194
  author =       {Daniel D. Sleator and Robert E. Tarjan},
kpeter@743
   195
  title =        {A data structure for dynamic trees},
kpeter@743
   196
  journal =      {Journal of Computer and System Sciences},
kpeter@743
   197
  year =         1983,
kpeter@743
   198
  volume =       26,
kpeter@743
   199
  number =       3,
kpeter@743
   200
  pages =        {362-391}
kpeter@743
   201
}
kpeter@743
   202
kpeter@743
   203
kpeter@743
   204
%%%%% Minimum mean cycle algorithms %%%%%
kpeter@743
   205
kpeter@743
   206
@article{karp78characterization,
kpeter@743
   207
  author =       {Richard M. Karp},
kpeter@743
   208
  title =        {A characterization of the minimum cycle mean in a
kpeter@743
   209
                  digraph},
kpeter@743
   210
  journal =      {Discrete Math.},
kpeter@743
   211
  year =         1978,
kpeter@743
   212
  volume =       23,
kpeter@743
   213
  pages =        {309-311}
kpeter@743
   214
}
kpeter@743
   215
kpeter@743
   216
@article{dasdan98minmeancycle,
kpeter@743
   217
  author =       {Ali Dasdan and Rajesh K. Gupta},
kpeter@743
   218
  title =        {Faster Maximum and Minimum Mean Cycle Alogrithms for
kpeter@743
   219
                  System Performance Analysis},
kpeter@743
   220
  journal =      {IEEE Transactions on Computer-Aided Design of
kpeter@743
   221
                  Integrated Circuits and Systems},
kpeter@743
   222
  year =         1998,
kpeter@743
   223
  volume =       17,
kpeter@743
   224
  number =       10,
kpeter@743
   225
  pages =        {889-899}
kpeter@743
   226
}
kpeter@743
   227
kpeter@743
   228
kpeter@743
   229
%%%%% Minimum cost flow algorithms %%%%%
kpeter@743
   230
kpeter@743
   231
@article{klein67primal,
kpeter@743
   232
  author =       {Morton Klein},
kpeter@743
   233
  title =        {A primal method for minimal cost flows with
kpeter@743
   234
                  applications to the assignment and transportation
kpeter@743
   235
                  problems},
kpeter@743
   236
  journal =      {Management Science},
kpeter@743
   237
  year =         1967,
kpeter@743
   238
  volume =       14,
kpeter@743
   239
  pages =        {205-220}
kpeter@743
   240
}
kpeter@743
   241
kpeter@755
   242
@article{goldberg89cyclecanceling,
kpeter@743
   243
  author =       {Andrew V. Goldberg and Robert E. Tarjan},
kpeter@743
   244
  title =        {Finding minimum-cost circulations by canceling
kpeter@743
   245
                  negative cycles},
kpeter@755
   246
  journal =      {Journal of the ACM},
kpeter@755
   247
  year =         1989,
kpeter@755
   248
  volume =       36,
kpeter@755
   249
  number =       4,
kpeter@755
   250
  pages =        {873-886}
kpeter@743
   251
}
kpeter@743
   252
kpeter@755
   253
@article{goldberg90approximation,
kpeter@743
   254
  author =       {Andrew V. Goldberg and Robert E. Tarjan},
kpeter@743
   255
  title =        {Finding Minimum-Cost Circulations by Successive
kpeter@743
   256
                  Approximation},
kpeter@743
   257
  journal =      {Mathematics of Operations Research},
kpeter@743
   258
  year =         1990,
kpeter@743
   259
  volume =       15,
kpeter@743
   260
  number =       3,
kpeter@743
   261
  pages =        {430-466}
kpeter@743
   262
}
kpeter@743
   263
kpeter@743
   264
@article{goldberg97efficient,
kpeter@743
   265
  author =       {Andrew V. Goldberg},
kpeter@743
   266
  title =        {An Efficient Implementation of a Scaling
kpeter@743
   267
                  Minimum-Cost Flow Algorithm},
kpeter@743
   268
  journal =      {Journal of Algorithms},
kpeter@743
   269
  year =         1997,
kpeter@743
   270
  volume =       22,
kpeter@743
   271
  number =       1,
kpeter@743
   272
  pages =        {1-29}
kpeter@743
   273
}
kpeter@743
   274
kpeter@743
   275
@article{bunnagel98efficient,
kpeter@743
   276
  author =       {Ursula B{\"u}nnagel and Bernhard Korte and Jens
kpeter@743
   277
                  Vygen},
kpeter@743
   278
  title =        {Efficient implementation of the {G}oldberg-{T}arjan
kpeter@743
   279
                  minimum-cost flow algorithm},
kpeter@743
   280
  journal =      {Optimization Methods and Software},
kpeter@743
   281
  year =         1998,
kpeter@743
   282
  volume =       10,
kpeter@743
   283
  pages =        {157-174}
kpeter@743
   284
}
kpeter@743
   285
kpeter@755
   286
@book{dantzig63linearprog,
kpeter@755
   287
  author =       {George B. Dantzig},
kpeter@755
   288
  title =        {Linear Programming and Extensions},
kpeter@755
   289
  publisher =    {Princeton University Press},
kpeter@755
   290
  year =         1963
kpeter@755
   291
}
kpeter@755
   292
kpeter@743
   293
@mastersthesis{kellyoneill91netsimplex,
kpeter@743
   294
  author =       {Damian J. Kelly and Garrett M. O'Neill},
kpeter@743
   295
  title =        {The Minimum Cost Flow Problem and The Network
kpeter@743
   296
                  Simplex Method},
kpeter@743
   297
  school =       {University College},
kpeter@743
   298
  address =      {Dublin, Ireland},
kpeter@743
   299
  year =         1991,
kpeter@743
   300
  month =        sep,
kpeter@743
   301
}