| <HTML> |
| <!-- |
| Copyright (c) Jeremy Siek 2000 |
| |
| Distributed under the Boost Software License, Version 1.0. |
| (See accompanying file LICENSE_1_0.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| --> |
| <Head> |
| <Title>Boost Graph Library: Bibliography</Title> |
| <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" |
| ALINK="#ff0000"> |
| <IMG SRC="../../../boost.png" |
| ALT="C++ Boost" width="277" height="86"> |
| |
| <BR Clear> |
| |
| |
| <H2>Bibliography</H2> |
| |
| <DL COMMapCT><DD><P></P><DT><A NAME="aho83:_data_struct_algo">1</A> |
| <DD> |
| A. V. Aho, J. E. Hopcroft, and J. D. Ullman. |
| <BR><EM>Data Structures and Algorithms</EM>. |
| <BR>Addison-Wesley, 1983. |
| |
| <P></P><DT><A NAME="austern99:_gener_progr_stl">2</A> |
| <DD> |
| M. H. Austern. |
| <BR><EM>Generic Programming and the STL</EM>. |
| <BR>Professional computing series. Addison-Wesley, 1999. |
| |
| <P></P><DT><A NAME="baumgartner95:_signatures">3</A> |
| <DD> |
| G. Baumgartner and V. F. Russo. |
| <BR>Signatures: A language extension for improving type abstraction and |
| subtype polymorphism in C++. |
| <BR><EM>Software-Practice and Experience</EM>, 25(8):863-889, August 1995. |
| |
| <P></P><DT><A NAME="bellman58">4</A> |
| <DD> |
| R. Bellman. |
| <BR>On a routing problem. |
| <BR><EM>Quarterly of Applied Mathematics</EM>, 16(1):87-90, 1958. |
| |
| <P></P><DT><A NAME="bruce95">5</A> |
| <DD> |
| K. B. Bruce, L. Cardelli, G. Castagna, the Hopkins Objects Group, G. T. |
| Leavens, and B. Pierce. |
| <BR>On binary methods. |
| <BR><EM>Theory and Practice of Object Systems</EM>, 1:221-242, 1995. |
| |
| <P></P><DT><A NAME="coleman85:_algor">6</A> |
| <DD> |
| T. F. Coleman, B. S. Garbow, and J. J. Mor'e. |
| <BR>Algorithm 649: Fortran subroutines for estimating sparse hessian |
| matrices. |
| <BR><EM>ACM Transactions on Mathematical Software</EM>, 11(4):378, December |
| 1985. |
| |
| <P></P><DT><A NAME="coleman84:_estim_jacob">7</A> |
| <DD> |
| T. F. Coleman and J. J. Mor'e. |
| <BR>Estimation of sparse jacobian matrices and graph coloring problems. |
| <BR><EM>SIAM Journal on Numerical Analysis</EM>, 20:187-209,, 1984. |
| |
| <P></P><DT><A NAME="clr90">8</A> |
| <DD> |
| T. Cormen, C. Leiserson, and R. Rivest. |
| <BR><EM>Introduction to Algorithms</EM>. |
| <BR>McGraw-Hill, 1990. |
| |
| <P></P><DT><A NAME="curtis74:_jacob">9</A> |
| <DD> |
| A. Curtis, M. Powell, and J. Reid. |
| <BR>On the estimation of sparse jacobian matrices. |
| <BR><EM>Journal of the Institute of Mathematics and its Applications</EM>, |
| 13:117-119, 1974. |
| |
| <P></P><DT><A NAME="dijkstra59">10</A> |
| <DD> |
| E. Dijkstra. |
| <BR>A note on two problems in connexion with graphs. |
| <BR><EM>Numerische Mathematik</EM>, 1:269-271, 1959. |
| |
| <P></P><DT><A NAME="ford62:_flows">11</A> |
| <DD> |
| L. R. Ford and D. R. Fulkerson. |
| <BR><EM>Flows in networks</EM>. |
| <BR>Princeton University Press, 1962. |
| |
| <P></P><DT><A NAME="gamma95:_design_patterns">12</A> |
| <DD> |
| E. Gamma, R. Helm, R. Johnson, and J. Vlissides. |
| <BR><EM>Design Patterns: Elements of Reusable Object-Oriented Software</EM>. |
| <BR>Professional Computing. Addison-Welsey, 1995. |
| |
| <P></P><DT><A NAME="george93:graphtheory">13</A> |
| <DD> |
| A. George, J. R. Gilbert, and J. W. Liu, editors. |
| <BR><EM>Graph Theory and Sparse Matrix Computation</EM>. |
| <BR>Springer-Verlag New York, Inc, 1993. |
| |
| <P></P><DT><A NAME="george81:__sparse_pos_def">14</A> |
| <DD> |
| A. George and J. W.-H. Liu. |
| <BR><EM>Computer Solution of Large Sparse Positive Definite Systems</EM>. |
| <BR>Computational Mathematics. Prentice-Hall, 1981. |
| |
| <P></P><DT><A NAME="graham85">15</A> |
| <DD> |
| R. Graham and P. Hell. |
| <BR>On the history of the minimum spanning tree problem. |
| <BR><EM>Annals of the History of Computing</EM>, 7(1):43-57, 1985. |
| |
| <P></P><DT><A NAME="hart68">16</A> |
| <DD> |
| P. E. Hart, N. J. Nilsson, and B. Raphael. |
| <BR>A formal basis for the heuristic determination of minimum cost paths. |
| <BR><EM>IEEE Transactions on Systems Science and Cybernetics</EM>, |
| 4(2):100-107, 1968. |
| |
| <P></P><DT><A NAME="kruskal56">18</A> |
| <DD> |
| J. B. Kruskal. |
| <BR>On the shortest spanning subtree of a graph and the traveling |
| salesman problem. |
| <BR>In <EM>Proceedings of the American Mathematical Sofiety</EM>, volume 7, |
| pages 48-50, 1956. |
| |
| <P></P><DT><A NAME="kuehl96:_design_patterns_for_graph_algo">19</A> |
| <DD> |
| D. Kühl. |
| <BR>Design patterns for the implementation of graph algorithms. |
| <BR>Master's thesis, Technische Universität Berlin, July 1996. |
| |
| <P></P><DT><A NAME="lawler76:_comb_opt">20</A> |
| <DD> |
| E. L. Lawler. |
| <BR><EM>Combinatorial Opimization: Networks and Matroids</EM>. |
| <BR>Holt, Rinehart, and Winston, 1976. |
| |
| <P></P><DT><A NAME="LIU:MMD">21</A> |
| <DD> |
| J. W. H. Liu. |
| <BR>Modification of the minimum-degree algorithm by multiple elimination. |
| <BR><EM>ACM Transaction on Mathematical Software</EM>, 11(2):141-153, 1985. |
| |
| <P></P><DT><A NAME="mehlhorn99:_leda">22</A> |
| <DD> |
| K. Mehlhorn and S. Näher. |
| <BR><EM>The LEDA Platform of Combinatorial and Geometric Computing</EM>. |
| <BR>Cambridge University Press, 1999. |
| |
| <P></P><DT><A NAME="meyer88:_object_soft_const">23</A> |
| <DD> |
| B. Meyer. |
| <BR><EM>Object-oriented Software Construction</EM>. |
| <BR>Prentice Hall International Series in Computer Science. Prentice |
| Hall, 1988. |
| |
| <P></P><DT><A NAME="myers95:_trait">24</A> |
| <DD> |
| N. C. Myers. |
| <BR>Traits: a new and useful template technique. |
| <BR><EM>C++ Report</EM>, June 1995. |
| |
| <P></P><DT><A NAME="prim57:_short">25</A> |
| <DD> |
| R. Prim. |
| <BR>Shortest connection networks and some generalizations. |
| <BR><EM>Bell System Technical Journal</EM>, 36:1389-1401, 1957. |
| |
| <P></P><DT><A NAME="saad96:imsms">26</A> |
| <DD> |
| Y. Saad. |
| <BR><EM>Iterative Methods for Sparse Minear System</EM>. |
| <BR>PWS Publishing Company, 1996. |
| |
| <P></P><DT><A NAME="tarjan83:_data_struct_network_algo">27</A> |
| <DD> |
| R. E. Tarjan. |
| <BR><EM>Data Structures and Network Algorithms</EM>. |
| <BR>Society for Industrial and Applied Mathematics, 1983. |
| |
| <P></P><DT><A NAME="parter61:_gauss">28</A> |
| <DD> |
| Seymour Parter. |
| <BR><EM>The use of linear graphs in Gauss elimination</EM>. |
| <BR>SIAM Review, 1961 3:119-130. |
| |
| <P></P><DT><A NAME="matula72:_graph_theory_computing">29</A> |
| <DD> |
| D. Matula, G. Marble, and J. Isaacson |
| <BR><EM>Graph coloring algorithms in Graph Theory and |
| Computing</EM>.<BR> |
| Academic Press, pp.104-122, 1972. |
| |
| <P></P><DT><A NAME="garey79:computers-and-intractability">30</a> |
| <DD> |
| M.R. Garey and D.S. Johnson<BR> |
| <EM>Computers and Intractibility: A Guide to the Theory of |
| NP-Completeness</EM><BR> |
| W.H. Freeman, New York, 1979. |
| |
| <P></P><DT><A NAME="welsch67">31</a> |
| <DD>D. Welsch and M. B. Powel<BR> |
| <EM>An upper bound for the chromatic number of a graph and its |
| application to timetabling problems</EM> |
| Computer Journal, 10:85-86, 1967. |
| |
| <P></P><DT><A NAME="brelaz79:_new">32</a> |
| <DD>D. Br'elaz<BR> |
| <EM>New methods to color the vertices of a graph</EM><br> |
| Communications of the ACM, vol. 22, 1979, pp. 251-256. |
| |
| <P></P><DT><A NAME="heber99:_saw">33</a> |
| <DD>G. Heber, R. Biswas, G.R. Gao<BR> |
| <EM>Self-Avoiding Walks over Adaptive Unstructured Grids</EM><br> |
| Parallel and Distributed Processing, LNCS 1586, |
| Springer-Verlag, 1999, pp. 968-977 |
| |
| |
| <P></P><DT><A NAME="ng-raghavan">34</a> |
| <DD>Esmond G. Ng amd Padma Raghavan<BR> |
| <EM>Performance of greedy ordering heuristics for sparse {C}holesky factorization</EM><br> |
| SIAM Journal on Matrix Analysis and Applications (To appear) |
| |
| <P></P><DT><A NAME="George:evolution">35</a> |
| <DD>Alan George and Joseph W. H. Liu<BR> |
| <EM>The Evolution of the Minimum Degree Ordering Algorithm</EM><br> |
| SIAM Review, March 1989, vol. 31, num. 1, pp. 1-19. |
| |
| <P></P><DT><A NAME="ford56:_maxim">36</a> |
| <DD>L. R. Ford and D. R. Fulkerson<BR> |
| <EM>Maximal flow through a network.</EM><br> |
| Can. Journal of Mathematics 1956 pp.399-404 |
| |
| <P></P><DT><A NAME="goldberg85:_new_max_flow_algor">37</a> |
| <DD>A. V. Goldberg<BR> |
| <EM>A New Max-Flow Algorithm.</EM><br> |
| MIT Tehnical report MIT/LCS/TM-291, 1985. |
| |
| <P></P><DT><A NAME="karzanov74:_deter">38</a> |
| <DD>A. V. Karzanov<BR> |
| <EM>Determining the maximal flow in a network by the method of preflows.</EM><br> |
| Sov. Math. Dokl. 1974 |
| |
| <P></P><DT><A NAME="ahuja93:_network_flows">39</a> |
| <DD>Ravindra K. Ahuja and Thomas L. Magnanti and James B. Orlin<BR> |
| <EM>Network Flows: Theory, Algorithms, and Applications.</EM><br> |
| Prentice Hall, 1993. |
| |
| <P></P><DT><A NAME="edmonds72:_improvements_netflow">40</a> |
| <DD>Jack Edmonds and Richard M. Karp<BR> |
| <EM>Theoretical improvements in the algorithmic efficiency for network flow problems.</EM><br> |
| Journal of the ACM, 1972 19:248-264 |
| |
| <P></P><DT><A NAME="tarjan72:dfs_and_linear_algo">41</a> |
| <DD>Robert E. Tarjan<BR> |
| <EM>Depth first search and linear graph algorithms.</EM><br> |
| SIAM Journal on Computing, 1(2):146-160, 1972 |
| |
| <P></P><DT><A NAME="eppstein97:dynamic_graph">42</a> |
| <DD>David Eppstein, Zvi Galil, and Giuseppe F. Italiano<BR> |
| <EM>Dynamic Graph Algorithms.</EM><br> |
| Chapter 22, CRC Handbook of Algorithms and Theory of Computation, 1997. |
| |
| <P></P><DT><A NAME="cuthill69:reducing_bandwith">43</a> |
| <DD>E. Cuthill and J. McKee<BR> |
| <EM>Reducing the bandwidth of sparse symmetric matrices.</EM><br> |
| Proceedings of the 24th National Conference of the ACM, 1969. |
| |
| <P></P><DT><A NAME="liu75:anal_cm_rcm">44</a> |
| <DD>J. Liu and A. Sherman<BR> |
| <EM>Comparative analysis of the Cuthill-Mckee and the reverse |
| Cuthill-Mckee ordering algorithms for sparse matrices.</EM><br> |
| SIAM Journal of Numerical Analysis. 13 (1975), pp. 198-213. |
| |
| <P></P><DT><A NAME="george71:fem">45</a> |
| <DD>Alan George<BR> |
| <EM>Computer implementation of the finite element method</EM><br> |
| Technical Report STAN-CS-208, Stanford University (1971). |
| |
| <P></P><DT><A NAME="fortin96:_graph_iso_prob">46</a> |
| <DD>Scott Fortin<BR> |
| <EM>The Graph Isomorphism Problem</EM><br> |
| TR 96-20, Dept. of Computer Science, University of Alberta (1996) |
| |
| <P></P><DT><A NAME="mckay81:_pract_graph_iso">47</a> |
| <DD>Brendan D. McKay<BR> |
| <EM>Practical Graph Isomorphism</EM><br> |
| Congressus Numerantium (1981) |
| |
| <P></P><DT><A NAME="reingold77:_combin_algo">48</a> |
| <DD>Reingold, Nievergelt, and Deo<BR> |
| <EM>Combinatorial Algorithms: Theory and Practice</EM><br> |
| Prentice Hall (1977) |
| |
| <P></P><DT><A NAME="moore59">49</a> |
| <DD>Edward Moore<BR> |
| <EM>The shortest path through a maze</EM><br> |
| International Symposium on the Theory of Switching (1959)<br> |
| Harvard University Press |
| |
| <P></P><DT><A NAME="nuutila95">50</a> |
| <DD>E. Nuutila<BR> |
| <EM>Efficient transitive closure computation in large digraphs</EM><br> |
| PhD Thesis, Helsinki University of Technology, 1995. <br> |
| Acta Polytechnica Scandinavica, Mathematics and Computing in |
| Engineering Series, No. 74. |
| |
| <P></P><DT><A NAME="goral79">51</a> |
| <DD>A. Goralcikova and V. Koubek<BR> |
| <EM>A reduct and closure algorithm for graphs</EM><br> |
| In Mathematical Foundations of Computer Science, <br> |
| volume 74 of Lecture Notes in Computer Science, pages 301-307. <br> |
| Springer-Verlag, 1979 |
| |
| <P></P><DT><A NAME="simon86">52</a> |
| <DD>Klaus Simon<BR> |
| <EM>An Improved Algorithm for Transitive Closure on Acyclic Digraphs</EM><br> |
| Theoretical Computer Science 58<br> |
| Automata, Languages and Programming, 376-386, 1986 |
| |
| <P></P><DT><A NAME="purdom70">53</a> |
| <DD>P. Purdom<BR> |
| <EM>A Transitive Closure Algorithm</EM><br> |
| BIT, 10, 1970, pp. 76-94. |
| |
| <p></p><dt><a name="brandes01">54</a> |
| <dd>Ulrik Brandes<br> |
| <em><a href="http://ella.slis.indiana.edu/~katy/L579/brandes.pdf">A |
| Faster Algorithm for Betweenness Centrality</a></em><br> |
| Journal of Mathematical Sociology 25 (2):163-177, 2001. |
| |
| <p></p><dt><a name="freeman77">55</a> |
| <dd>Lindon C. Freeman<br> |
| <em>A Set of Measures of Centrality Based on Betweenness</em><br> |
| Sociometry 40, pp. 35-41, 1977. |
| |
| <p></p><dt><a name="anthonisse71">56</a> |
| <dd>J.M. Anthonisse<br> |
| <em>The rush in a directed graph.</em><br> |
| Technical Report BN9/71, Stichting Mahtematisch Centrum, Amsterdam, 1971. |
| |
| <p></p><dt><a name="kamada89">57</a> |
| <dd>T. Kamada and S. Kawai<br> |
| <em>An algorithm for drawing general undirected graphs.</em><br> |
| Information Processing Letters, 31, pp. 7-15, 1989. |
| |
| <p></p><dt><a name="fruchterman91">58</a> |
| <dd>T. Fruchterman and E. Reingold<br> |
| <em>Graph drawing by force-directed placement.</em><br> |
| Software--Practice & Experience, 21 (11), pp. 1129-1164, 1991. |
| |
| <p></p><dt><a name="coleman83">59</a> |
| <dd>Thomas F. Coleman and Jorge J. More<br> |
| <em>Estimation of sparse Jacobian |
| matrices and graph coloring problems.</em><br> |
| Journal of Numerical Analasis V20, pp. 187-209, 1983. |
| |
| <p></p><dt><a name="gursoy00">60</a> |
| <dd>Attila Gürsoy and Murat Atun<br> |
| <em>Neighborhood Preserving Load Balancing: A Self-Organizing Approach</em> |
| <br> |
| Euro-Par Parallel Processing, LNCS 1900, pp. 324-41, 2000. |
| |
| <p></p><dt><a name="driscoll88">61</a> |
| <dd>James R. Driscoll, Harold N. Gabow, Ruth Shrairman, and Robert E. Tarjan<br> |
| <em>Relaxed Heaps: An alternative for Fibonacci Heaps with applications to parallel computation.</em><br> |
| Communications of the ACM, 31 (11), pp. 1343-1354, November 1988. |
| |
| <p></p><dt><a name="king70">62</a> |
| <dd>King, I. P.<br> |
| <em>An automatic reordering scheme for simultaneous equations derived from network analysis.</em><br> |
| Int. J. Numer. Methods Engrg. 2, pp. 523-533, 1970. |
| |
| <p></p><dt><a name="palmer2000">63</a> |
| <dd>C. Palmer and J. Steffan<br> |
| <em>Generating Network Topologies That Obey Power Laws</em><br> |
| Proceedings of GLOBECOM. November, 2000. |
| |
| <p></p><dt><a name="edmonds65">64</a> |
| <dd>J. Edmonds<br> |
| <em>Paths, trees, and flowers</em><br> |
| Canadian Journal of Mathematics 17 (1965), pp. 449-467. |
| |
| <p></p><dt><a name="lengauer-tarjan79">65</a> |
| <dd>Thomas Lengauer and Robert Endre Tarjan<br> |
| <em>A fast algorithm for finding dominators in a flowgraph</em><br> |
| ACM Transactions on Programming Language and Systems, 1(1):121-141, 1979. |
| |
| <p></p><dt><a name="muchnick97">66</a> |
| <dd>Steven S. Muchnick<br> |
| <em>Advanced Compiler Design and Implementation</em><br> |
| Morgan Kaufmann Publishers, San Fransisco, 1997. |
| |
| <p></p><dt><a name="appel98">67</a> |
| <dd>Andrew W. Appel<br> |
| <em>Modern Compiler Implementation in JAVA</em><br> |
| Cambridge University Press, 1998. |
| |
| <p></p><dt><a name="kolmogorov03">68</a> |
| <dd>Vladimir Kolmogorov<br> |
| <em>Graph Based Algorithms for Scene Reconstruction from Two or More Views</em><br> |
| PhD thesis, Cornell University, September 2003. |
| |
| <p></p><dt><a name="boykov-kolmogorov04">69</a> |
| <dd>Yuri Boykov and Vladimir Kolmogorov<br> |
| <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> |
| In <em>IEEE Transactions on Pattern Analysis and Machine Intelligence</em>, vol. 26, no. 9, pp. 1124-1137, Sept. 2004. |
| |
| <p></p><dt><a name="boyermyrvold04">70</a> |
| <dd>John M. Boyer and Wendy J. Myrvold<br> |
| <em><a href="http://www.emis.de/journals/JGAA/accepted/2004/BoyerMyrvold2004.8.3.pdf"> |
| On the Cutting Edge: Simplified O(n) Planarity by Edge Addition</a> |
| </em><br> |
| Journal of Graph Algorithms and Applications, 8(2): 241-273, 2004. |
| |
| <p></p><dt><a name="chrobakpayne95">71</a> |
| <dd>M. Chrobak, T. Payne<br> |
| <em> |
| A Linear-time Algorithm for Drawing a Planar Graph on the Grid |
| </em><br> |
| Information Processing Letters 54: 241-246, 1995. |
| |
| <p></p><dt><a name="defraysseixpachpollack90">72</a> |
| <dd>H. de Fraysseix, J. Pach, R. Pollack<br> |
| <em> |
| How to Draw a Planar Graph on a Grid |
| </em><br> |
| Combinatorica 10: 41-51, 1990. |
| |
| <P></P><DT><A NAME="wilson96generating">73</A> |
| <DD> |
| David Bruce Wilson |
| <BR><em>Generating random spanning trees more quickly than the cover time</em>. |
| ACM Symposium on the Theory of Computing, pp. 296-303, 1996. |
| |
| </dl> |
| |
| <br> |
| <HR> |
| <TABLE> |
| <TR valign=top> |
| <TD nowrap>Copyright © 2000-2001</TD><TD> |
| <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>) |
| </TD></TR></TABLE> |
| |
| </BODY> |
| </HTML> |