ceph/src/boost/libs/graph/doc/bibliography.html

   1 <HTML>
   2 <!--
   3      Copyright (c) Jeremy Siek 2000
   4
   5      Distributed under the Boost Software License, Version 1.0.
   6      (See accompanying file LICENSE_1_0.txt or copy at
   7      http://www.boost.org/LICENSE_1_0.txt)
   8   -->
   9 <Head>
  10 <Title>Boost Graph Library: Bibliography</Title>
  11 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  12         ALINK="#ff0000">
  13 <IMG SRC="../../../boost.png"
  14      ALT="C++ Boost" width="277" height="86">
  15
  16 <BR Clear>
  17
  18
  19 <H2>Bibliography</H2>
  20
  21 <DL COMMapCT><DD><P></P><DT><A NAME="aho83:_data_struct_algo">1</A>
  22 <DD>
  23 A.&nbsp;V. Aho, J.&nbsp;E. Hopcroft, and J.&nbsp;D. Ullman.
  24 <BR><EM>Data Structures and Algorithms</EM>.
  25 <BR>Addison-Wesley, 1983.
  26
  27 <P></P><DT><A NAME="austern99:_gener_progr_stl">2</A>
  28 <DD>
  29 M.&nbsp;H. Austern.
  30 <BR><EM>Generic Programming and the STL</EM>.
  31 <BR>Professional computing series. Addison-Wesley, 1999.
  32
  33 <P></P><DT><A NAME="baumgartner95:_signatures">3</A>
  34 <DD>
  35 G.&nbsp;Baumgartner and V.&nbsp;F. Russo.
  36 <BR>Signatures: A language extension for improving type abstraction and
  37   subtype polymorphism in C++.
  38 <BR><EM>Software-Practice and Experience</EM>, 25(8):863-889, August 1995.
  39
  40 <P></P><DT><A NAME="bellman58">4</A>
  41 <DD>
  42 R.&nbsp;Bellman.
  43 <BR>On a routing problem.
  44 <BR><EM>Quarterly of Applied Mathematics</EM>, 16(1):87-90, 1958.
  45
  46 <P></P><DT><A NAME="bruce95">5</A>
  47 <DD>
  48 K.&nbsp;B. Bruce, L.&nbsp;Cardelli, G.&nbsp;Castagna, the Hopkins Objects&nbsp;Group, G.&nbsp;T.
  49   Leavens, and B.&nbsp;Pierce.
  50 <BR>On binary methods.
  51 <BR><EM>Theory and Practice of Object Systems</EM>, 1:221-242, 1995.
  52
  53 <P></P><DT><A NAME="coleman85:_algor">6</A>
  54 <DD>
  55 T.&nbsp;F. Coleman, B.&nbsp;S. Garbow, and J.&nbsp;J. Mor'e.
  56 <BR>Algorithm 649: Fortran subroutines for estimating sparse hessian
  57   matrices.
  58 <BR><EM>ACM Transactions on Mathematical Software</EM>, 11(4):378, December
  59   1985.
  60
  61 <P></P><DT><A NAME="coleman84:_estim_jacob">7</A>
  62 <DD>
  63 T.&nbsp;F. Coleman and J.&nbsp;J. Mor'e.
  64 <BR>Estimation of sparse jacobian matrices and graph coloring problems.
  65 <BR><EM>SIAM Journal on Numerical Analysis</EM>, 20:187-209,, 1984.
  66
  67 <P></P><DT><A NAME="clr90">8</A>
  68 <DD>
  69 T.&nbsp;Cormen, C.&nbsp;Leiserson, and R.&nbsp;Rivest.
  70 <BR><EM>Introduction to Algorithms</EM>.
  71 <BR>McGraw-Hill, 1990.
  72
  73 <P></P><DT><A NAME="curtis74:_jacob">9</A>
  74 <DD>
  75 A.&nbsp;Curtis, M.&nbsp;Powell, and J.&nbsp;Reid.
  76 <BR>On the estimation of sparse jacobian matrices.
  77 <BR><EM>Journal of the Institute of Mathematics and its Applications</EM>,
  78   13:117-119, 1974.
  79
  80 <P></P><DT><A NAME="dijkstra59">10</A>
  81 <DD>
  82 E.&nbsp;Dijkstra.
  83 <BR>A note on two problems in connexion with graphs.
  84 <BR><EM>Numerische Mathematik</EM>, 1:269-271, 1959.
  85
  86 <P></P><DT><A NAME="ford62:_flows">11</A>
  87 <DD>
  88 L.&nbsp;R. Ford and D.&nbsp;R. Fulkerson.
  89 <BR><EM>Flows in networks</EM>.
  90 <BR>Princeton University Press, 1962.
  91
  92 <P></P><DT><A NAME="gamma95:_design_patterns">12</A>
  93 <DD>
  94 E.&nbsp;Gamma, R.&nbsp;Helm, R.&nbsp;Johnson, and J.&nbsp;Vlissides.
  95 <BR><EM>Design Patterns: Elements of Reusable Object-Oriented Software</EM>.
  96 <BR>Professional Computing. Addison-Welsey, 1995.
  97
  98 <P></P><DT><A NAME="george93:graphtheory">13</A>
  99 <DD>
 100 A.&nbsp;George, J.&nbsp;R. Gilbert, and J.&nbsp;W. Liu, editors.
 101 <BR><EM>Graph Theory and Sparse Matrix Computation</EM>.
 102 <BR>Springer-Verlag New York, Inc, 1993.
 103
 104 <P></P><DT><A NAME="george81:__sparse_pos_def">14</A>
 105 <DD>
 106 A.&nbsp;George and J.&nbsp;W.-H. Liu.
 107 <BR><EM>Computer Solution of Large Sparse Positive Definite Systems</EM>.
 108 <BR>Computational Mathematics. Prentice-Hall, 1981.
 109
 110 <P></P><DT><A NAME="graham85">15</A>
 111 <DD>
 112 R.&nbsp;Graham and P.&nbsp;Hell.
 113 <BR>On the history of the minimum spanning tree problem.
 114 <BR><EM>Annals of the History of Computing</EM>, 7(1):43-57, 1985.
 115
 116 <P></P><DT><A NAME="hart68">16</A>
 117 <DD>
 118 P.&nbsp;E. Hart, N.&nbsp;J. Nilsson, and B.&nbsp;Raphael.
 119 <BR>A formal basis for the heuristic determination of minimum cost paths.
 120 <BR><EM>IEEE Transactions on Systems Science and Cybernetics</EM>,
 121   4(2):100-107, 1968.
 122
 123 <P></P><DT><A NAME="kruskal56">18</A>
 124 <DD>
 125 J.&nbsp;B. Kruskal.
 126 <BR>On the shortest spanning subtree of a graph and the traveling
 127   salesman problem.
 128 <BR>In <EM>Proceedings of the American Mathematical Sofiety</EM>, volume&nbsp;7,
 129   pages 48-50, 1956.
 130
 131 <P></P><DT><A NAME="kuehl96:_design_patterns_for_graph_algo">19</A>
 132 <DD>
 133 D.&nbsp;K&#252;hl.
 134 <BR>Design patterns for the implementation of graph algorithms.
 135 <BR>Master's thesis, Technische Universit&#228;t Berlin, July 1996.
 136
 137 <P></P><DT><A NAME="lawler76:_comb_opt">20</A>
 138 <DD>
 139 E.&nbsp;L. Lawler.
 140 <BR><EM>Combinatorial Opimization: Networks and Matroids</EM>.
 141 <BR>Holt, Rinehart, and Winston, 1976.
 142
 143 <P></P><DT><A NAME="LIU:MMD">21</A>
 144 <DD>
 145 J.&nbsp;W.&nbsp;H. Liu.
 146 <BR>Modification of the minimum-degree algorithm by multiple elimination.
 147 <BR><EM>ACM Transaction on Mathematical Software</EM>, 11(2):141-153, 1985.
 148
 149 <P></P><DT><A NAME="mehlhorn99:_leda">22</A>
 150 <DD>
 151 K.&nbsp;Mehlhorn and S.&nbsp;Näher.
 152 <BR><EM>The LEDA Platform of Combinatorial and Geometric Computing</EM>.
 153 <BR>Cambridge University Press, 1999.
 154
 155 <P></P><DT><A NAME="meyer88:_object_soft_const">23</A>
 156 <DD>
 157 B.&nbsp;Meyer.
 158 <BR><EM>Object-oriented Software Construction</EM>.
 159 <BR>Prentice Hall International Series in Computer Science. Prentice
 160   Hall, 1988.
 161
 162 <P></P><DT><A NAME="myers95:_trait">24</A>
 163 <DD>
 164 N.&nbsp;C. Myers.
 165 <BR>Traits: a new and useful template technique.
 166 <BR><EM>C++ Report</EM>, June 1995.
 167
 168 <P></P><DT><A NAME="prim57:_short">25</A>
 169 <DD>
 170 R.&nbsp;Prim.
 171 <BR>Shortest connection networks and some generalizations.
 172 <BR><EM>Bell System Technical Journal</EM>, 36:1389-1401, 1957.
 173
 174 <P></P><DT><A NAME="saad96:imsms">26</A>
 175 <DD>
 176 Y.&nbsp;Saad.
 177 <BR><EM>Iterative Methods for Sparse Minear System</EM>.
 178 <BR>PWS Publishing Company, 1996.
 179
 180 <P></P><DT><A NAME="tarjan83:_data_struct_network_algo">27</A>
 181 <DD>
 182 R.&nbsp;E. Tarjan.
 183 <BR><EM>Data Structures and Network Algorithms</EM>.
 184 <BR>Society for Industrial and Applied Mathematics, 1983.
 185
 186 <P></P><DT><A NAME="parter61:_gauss">28</A>
 187 <DD>
 188 Seymour Parter.
 189 <BR><EM>The use of linear graphs in Gauss elimination</EM>.
 190 <BR>SIAM Review, 1961 3:119-130.
 191
 192 <P></P><DT><A NAME="matula72:_graph_theory_computing">29</A>
 193 <DD>
 194 D. Matula, G. Marble, and J. Isaacson
 195 <BR><EM>Graph coloring algorithms in Graph Theory and
 196 Computing</EM>.<BR>
 197 Academic Press, pp.104-122, 1972.
 198
 199 <P></P><DT><A NAME="garey79:computers-and-intractability">30</a>
 200 <DD>
 201 M.R. Garey and D.S. Johnson<BR>
 202 <EM>Computers and Intractibility: A Guide to the Theory of
 203 NP-Completeness</EM><BR>
 204 W.H. Freeman, New York, 1979.
 205
 206 <P></P><DT><A NAME="welsch67">31</a>
 207 <DD>D. Welsch and M. B. Powel<BR>
 208 <EM>An upper bound for the chromatic number of a graph and its
 209 application to timetabling problems</EM>
 210 Computer Journal, 10:85-86, 1967.
 211
 212 <P></P><DT><A NAME="brelaz79:_new">32</a>
 213 <DD>D. Br'elaz<BR>
 214 <EM>New methods to color the vertices of a graph</EM><br>
 215 Communications of the ACM, vol. 22, 1979, pp. 251-256.
 216
 217 <P></P><DT><A NAME="heber99:_saw">33</a>
 218 <DD>G. Heber, R. Biswas, G.R. Gao<BR>
 219 <EM>Self-Avoiding Walks over Adaptive Unstructured Grids</EM><br>
 220 Parallel and Distributed Processing, LNCS 1586,
 221 Springer-Verlag, 1999, pp. 968-977
 222
 223
 224 <P></P><DT><A NAME="ng-raghavan">34</a>
 225 <DD>Esmond G. Ng amd Padma Raghavan<BR>
 226 <EM>Performance of greedy ordering heuristics for sparse {C}holesky factorization</EM><br>
 227 SIAM Journal on Matrix Analysis and Applications (To appear)
 228
 229 <P></P><DT><A NAME="George:evolution">35</a>
 230 <DD>Alan George and Joseph W. H. Liu<BR>
 231 <EM>The Evolution of the Minimum Degree Ordering Algorithm</EM><br>
 232 SIAM Review, March 1989, vol. 31, num. 1, pp. 1-19.
 233
 234 <P></P><DT><A NAME="ford56:_maxim">36</a>
 235 <DD>L. R. Ford and D. R. Fulkerson<BR>
 236 <EM>Maximal flow through a network.</EM><br>
 237 Can. Journal of Mathematics 1956 pp.399-404
 238
 239 <P></P><DT><A NAME="goldberg85:_new_max_flow_algor">37</a>
 240 <DD>A. V. Goldberg<BR>
 241 <EM>A New Max-Flow Algorithm.</EM><br>
 242 MIT Tehnical report MIT/LCS/TM-291, 1985.
 243
 244 <P></P><DT><A NAME="karzanov74:_deter">38</a>
 245 <DD>A. V. Karzanov<BR>
 246 <EM>Determining the maximal flow in a network by the method of preflows.</EM><br>
 247 Sov. Math. Dokl. 1974
 248
 249 <P></P><DT><A NAME="ahuja93:_network_flows">39</a>
 250 <DD>Ravindra K. Ahuja and Thomas L. Magnanti and James B. Orlin<BR>
 251 <EM>Network Flows: Theory, Algorithms, and Applications.</EM><br>
 252 Prentice Hall, 1993.
 253
 254 <P></P><DT><A NAME="edmonds72:_improvements_netflow">40</a>
 255 <DD>Jack Edmonds and Richard M. Karp<BR>
 256 <EM>Theoretical improvements in the algorithmic efficiency for network flow problems.</EM><br>
 257 Journal of the ACM, 1972 19:248-264
 258
 259 <P></P><DT><A NAME="tarjan72:dfs_and_linear_algo">41</a>
 260 <DD>Robert E. Tarjan<BR>
 261 <EM>Depth first search and linear graph algorithms.</EM><br>
 262 SIAM Journal on Computing, 1(2):146-160, 1972
 263
 264 <P></P><DT><A NAME="eppstein97:dynamic_graph">42</a>
 265 <DD>David Eppstein, Zvi Galil, and Giuseppe F. Italiano<BR>
 266 <EM>Dynamic Graph Algorithms.</EM><br>
 267 Chapter 22, CRC Handbook of Algorithms and Theory of Computation, 1997.
 268
 269 <P></P><DT><A NAME="cuthill69:reducing_bandwith">43</a>
 270 <DD>E. Cuthill and J. McKee<BR>
 271 <EM>Reducing the bandwidth of sparse symmetric matrices.</EM><br>
 272 Proceedings of the 24th National Conference of the ACM, 1969.
 273
 274 <P></P><DT><A NAME="liu75:anal_cm_rcm">44</a>
 275 <DD>J. Liu and A. Sherman<BR>
 276 <EM>Comparative analysis of the Cuthill-Mckee and the reverse
 277 Cuthill-Mckee ordering algorithms for sparse matrices.</EM><br>
 278 SIAM Journal of Numerical Analysis. 13 (1975), pp. 198-213.
 279
 280 <P></P><DT><A NAME="george71:fem">45</a>
 281 <DD>Alan George<BR>
 282 <EM>Computer implementation of the finite element method</EM><br>
 283 Technical Report STAN-CS-208, Stanford University (1971).
 284
 285 <P></P><DT><A NAME="fortin96:_graph_iso_prob">46</a>
 286 <DD>Scott Fortin<BR>
 287 <EM>The Graph Isomorphism Problem</EM><br>
 288 TR 96-20, Dept. of Computer Science, University of Alberta (1996)
 289
 290 <P></P><DT><A NAME="mckay81:_pract_graph_iso">47</a>
 291 <DD>Brendan D. McKay<BR>
 292 <EM>Practical Graph Isomorphism</EM><br>
 293 Congressus Numerantium (1981)
 294
 295 <P></P><DT><A NAME="reingold77:_combin_algo">48</a>
 296 <DD>Reingold, Nievergelt, and Deo<BR>
 297 <EM>Combinatorial Algorithms: Theory and Practice</EM><br>
 298 Prentice Hall (1977)
 299
 300 <P></P><DT><A NAME="moore59">49</a>
 301 <DD>Edward Moore<BR>
 302 <EM>The shortest path through a maze</EM><br>
 303 International Symposium on the Theory of Switching (1959)<br>
 304 Harvard University Press
 305
 306 <P></P><DT><A NAME="nuutila95">50</a>
 307 <DD>E. Nuutila<BR>
 308 <EM>Efficient transitive closure computation in large digraphs</EM><br>
 309 PhD Thesis, Helsinki University of Technology, 1995. <br>
 310 Acta Polytechnica Scandinavica, Mathematics and Computing in
 311 Engineering Series, No. 74.
 312
 313 <P></P><DT><A NAME="goral79">51</a>
 314 <DD>A. Goralcikova and V. Koubek<BR>
 315 <EM>A reduct and closure algorithm for graphs</EM><br>
 316 In Mathematical Foundations of Computer Science, <br>
 317 volume 74 of Lecture Notes in Computer Science, pages 301-307. <br>
 318 Springer-Verlag, 1979
 319
 320 <P></P><DT><A NAME="simon86">52</a>
 321 <DD>Klaus Simon<BR>
 322 <EM>An Improved Algorithm for Transitive Closure on Acyclic Digraphs</EM><br>
 323 Theoretical Computer Science 58<br>
 324 Automata, Languages and Programming, 376-386, 1986
 325
 326 <P></P><DT><A NAME="purdom70">53</a>
 327 <DD>P. Purdom<BR>
 328 <EM>A Transitive Closure Algorithm</EM><br>
 329 BIT, 10, 1970, pp. 76-94.
 330
 331 <p></p><dt><a name="brandes01">54</a>
 332 <dd>Ulrik Brandes<br>
 333 <em><a href="http://ella.slis.indiana.edu/~katy/L579/brandes.pdf">A
 334             Faster Algorithm for Betweenness Centrality</a></em><br>
 335 Journal of Mathematical Sociology 25 (2):163-177, 2001.
 336
 337 <p></p><dt><a name="freeman77">55</a>
 338 <dd>Lindon C. Freeman<br>
 339 <em>A Set of Measures of Centrality Based on Betweenness</em><br>
 340 Sociometry 40, pp. 35-41, 1977.
 341
 342 <p></p><dt><a name="anthonisse71">56</a>
 343 <dd>J.M. Anthonisse<br>
 344 <em>The rush in a directed graph.</em><br>
 345 Technical Report BN9/71, Stichting Mahtematisch Centrum, Amsterdam, 1971.
 346
 347 <p></p><dt><a name="kamada89">57</a>
 348 <dd>T. Kamada and S. Kawai<br>
 349 <em>An algorithm for drawing general undirected graphs.</em><br>
 350 Information Processing Letters, 31, pp. 7-15, 1989.
 351
 352 <p></p><dt><a name="fruchterman91">58</a>
 353 <dd>T. Fruchterman and E. Reingold<br>
 354   <em>Graph drawing by force-directed placement.</em><br>
 355 Software--Practice &amp; Experience, 21 (11), pp. 1129-1164, 1991.
 356
 357 <p></p><dt><a name="coleman83">59</a>
 358 <dd>Thomas F. Coleman and Jorge J. More<br>
 359   <em>Estimation of sparse Jacobian
 360    matrices and graph coloring problems.</em><br>
 361   Journal of Numerical Analasis V20, pp. 187-209, 1983.
 362
 363 <p></p><dt><a name="gursoy00">60</a>
 364 <dd>Attila G&uuml;rsoy and Murat Atun<br>
 365   <em>Neighborhood Preserving Load Balancing: A Self-Organizing Approach</em>
 366   <br>
 367   Euro-Par Parallel Processing, LNCS 1900, pp. 324-41, 2000.
 368
 369 <p></p><dt><a name="driscoll88">61</a>
 370 <dd>James R. Driscoll, Harold N. Gabow, Ruth Shrairman, and Robert E. Tarjan<br>
 371   <em>Relaxed Heaps: An alternative for Fibonacci Heaps with applications to parallel computation.</em><br>
 372   Communications of the ACM, 31 (11), pp. 1343-1354, November 1988.
 373
 374 <p></p><dt><a name="king70">62</a>
 375 <dd>King, I. P.<br>
 376 <em>An automatic reordering scheme for simultaneous equations derived from network analysis.</em><br>
 377 Int. J. Numer. Methods Engrg. 2, pp. 523-533, 1970.
 378
 379 <p></p><dt><a name="palmer2000">63</a>
 380 <dd>C. Palmer and J. Steffan<br>
 381 <em>Generating Network Topologies That Obey Power Laws</em><br>
 382 Proceedings of GLOBECOM. November, 2000.
 383
 384 <p></p><dt><a name="edmonds65">64</a>
 385 <dd>J. Edmonds<br>
 386 <em>Paths, trees, and flowers</em><br>
 387 Canadian Journal of Mathematics 17 (1965), pp. 449-467.
 388
 389 <p></p><dt><a name="lengauer-tarjan79">65</a>
 390 <dd>Thomas Lengauer and Robert Endre Tarjan<br>
 391 <em>A fast algorithm for finding dominators in a flowgraph</em><br>
 392 ACM Transactions on Programming Language and Systems, 1(1):121-141, 1979.
 393
 394 <p></p><dt><a name="muchnick97">66</a>
 395 <dd>Steven S. Muchnick<br>
 396 <em>Advanced Compiler Design and Implementation</em><br>
 397 Morgan Kaufmann Publishers, San Fransisco, 1997.
 398
 399 <p></p><dt><a name="appel98">67</a>
 400 <dd>Andrew W. Appel<br>
 401 <em>Modern Compiler Implementation in JAVA</em><br>
 402 Cambridge University Press, 1998.
 403
 404 <p></p><dt><a name="kolmogorov03">68</a>
 405 <dd>Vladimir Kolmogorov<br>
 406 <em>Graph Based Algorithms for Scene Reconstruction from Two or More Views</em><br>
 407 PhD thesis, Cornell University, September 2003.
 408
 409 <p></p><dt><a name="boykov-kolmogorov04">69</a>
 410   <dd>Yuri Boykov and Vladimir Kolmogorov<br>
 411     <em><a href="http://www.csd.uwo.ca/faculty/yuri/Abstracts/pami04-abs.html">An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision</a></em><br>
 412     In <em>IEEE Transactions on Pattern Analysis and Machine Intelligence</em>, vol. 26, no. 9, pp. 1124-1137, Sept. 2004.
 413
 414 <p></p><dt><a name="boyermyrvold04">70</a>
 415 <dd>John M. Boyer and Wendy J. Myrvold<br>
 416 <em><a href="http://www.emis.de/journals/JGAA/accepted/2004/BoyerMyrvold2004.8.3.pdf">
 417 On the Cutting Edge: Simplified O(n) Planarity by Edge Addition</a>
 418 </em><br>
 419 Journal of Graph Algorithms and Applications, 8(2): 241-273, 2004.
 420
 421 <p></p><dt><a name="chrobakpayne95">71</a>
 422 <dd>M. Chrobak, T. Payne<br>
 423 <em>
 424 A Linear-time Algorithm for Drawing a Planar Graph on the Grid
 425 </em><br>
 426 Information Processing Letters 54: 241-246, 1995.
 427
 428 <p></p><dt><a name="defraysseixpachpollack90">72</a>
 429 <dd>H. de Fraysseix, J. Pach, R. Pollack<br>
 430 <em>
 431 How to Draw a Planar Graph on a Grid
 432 </em><br>
 433 Combinatorica 10: 41-51, 1990.
 434
 435 <P></P><DT><A NAME="wilson96generating">73</A>
 436 <DD>
 437 David&nbsp;Bruce&nbsp;Wilson
 438 <BR><em>Generating random spanning trees more quickly than the cover time</em>.
 439 ACM Symposium on the Theory of Computing, pp. 296-303, 1996.
 440
 441 </dl>
 442
 443 <br>
 444 <HR>
 445 <TABLE>
 446 <TR valign=top>
 447 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 448 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
 449 </TD></TR></TABLE>
 450
 451 </BODY>
 452 </HTML>