mirror of
https://github.com/boostorg/graph.git
synced 2026-01-21 04:52:18 +00:00
347 lines
12 KiB
HTML
347 lines
12 KiB
HTML
<HTML>
|
|
<!--
|
|
-- Copyright (c) Jeremy Siek 2000
|
|
--
|
|
-- Permission to use, copy, modify, distribute and sell this software
|
|
-- and its documentation for any purpose is hereby granted without fee,
|
|
-- provided that the above copyright notice appears in all copies and
|
|
-- that both that copyright notice and this permission notice appear
|
|
-- in supporting documentation. Silicon Graphics makes no
|
|
-- representations about the suitability of this software for any
|
|
-- purpose. It is provided "as is" without express or implied warranty.
|
|
-->
|
|
<Head>
|
|
<Title>Boost Graph Library: Bibliography</Title>
|
|
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
|
|
ALINK="#ff0000">
|
|
<IMG SRC="../../../c++boost.gif"
|
|
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.
|
|
|
|
</DL>
|
|
|
|
<br>
|
|
<HR>
|
|
<TABLE>
|
|
<TR valign=top>
|
|
<TD nowrap>Copyright © 2000-2001</TD><TD>
|
|
<A HREF="../../../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>
|