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