123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467 |
- <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.
- <p></p><dt><a name="edmonds65:_max_weighted_match">74</a>
- <dd>J. Edmonds<br>
- <em>Maximum Matching and a Polyhedron with 0, 1-Vertices</em><br>
- Journal of Research of the National Bureau of Standards B 69, pp. 125-130, 1965.
- <p></p><dt><a name="gabow76">75</a>
- <dd>Harold N. Gabow<br>
- <em>An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs</em><br>
- Journal of the ACM (JACM), 23(2): 221-234, 1976.
- <p></p><dt><a name="gabow90">76</a>
- <dd>Harold N. Gabow<br>
- <em>Data Structures for Weighted Matching and Nearest Common Ancestors with Linking</em><br>
- Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 434-443, 1990.
- </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>
|