X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=biblio.bib;h=10335d477189d1202b194b9ef173da29808d203a;hb=e4ece93696bd08db4ef45ed8b29e76ba6c7848c4;hp=4bcfdef6f4a42c14084fa6851a8fa5fb808451cf;hpb=27749502e55ddcb33010db5294e13f0ff2728668;p=saga.git

diff --git a/biblio.bib b/biblio.bib
index 4bcfdef..10335d4 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -1,8 +1,8 @@
-@inproceedings{ bender00lca,
+@inproceedings{ bender:lca,
     author = "Michael A. Bender and Martin Farach-Colton",
     title = "The {LCA} Problem Revisited",
     booktitle = "Latin American Theoretical {INformatics}",
-    pages = "88-94",
+    pages = "88--94",
     year = "2000",
     url = "citeseer.ist.psu.edu/bender00lca.html" }
 
@@ -10,7 +10,7 @@
     author = "Greg N. Frederickson",
     title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and $k$ Smallest Spanning Trees",
     booktitle = "{IEEE} Symposium on Foundations of Computer Science",
-    pages = "632-641",
+    pages = "632--641",
     year = "1991",
     url = "citeseer.ist.psu.edu/frederickson91ambivalent.html" }
 
@@ -203,6 +203,18 @@
    year = "2004"
 }
 
+@inproceedings{ mm:rank,
+  author = "Martin Mare\v{s} and Milan Straka",
+  title = "Linear-Time Ranking of Permutations",
+  booktitle = "Algorithms --- ESA 2007: 15th Annual European Symposium",
+  location = "Eilat, Israel, October 8--10, 2007",
+  volume = "4698",
+  series = "Lecture Notes in Computer Science",
+  pages = "187--193",
+  publisher = "Springer",
+  year = "2007",
+}
+
 @article{ ft:fibonacci,
  author = {Michael L. Fredman and Robert Endre Tarjan},
  title = {Fibonacci heaps and their uses in improved network optimization algorithms},
@@ -284,15 +296,6 @@
   publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co.}
 }
 
-@article{ thorup:pq,
-  title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
-  author={Thorup, M.},
-  journal={Proceedings of the thirty-fifth ACM Symposium on Theory of Computing},
-  pages={149--158},
-  year={2003},
-  publisher={ACM Press New York, NY, USA}
-}
-
 @article{ graham:msthistory,
   title={{On the history of the minimum spanning tree problem}},
   author={Graham, R.L. and Hell, P.},
@@ -448,7 +451,7 @@ inproceedings{ pettie:minirand,
 @inproceedings{ katriel:cycle,
   author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
   title = "A practical minimum spanning tree algorithm using the cycle property",
-  booktitle = "11th European Symposium on Algorithms(ESA)",
+  booktitle = "11th European Symposium on Algorithms (ESA)",
   number = "2832",
   series = "LNCS",
   pages = "679--690",
@@ -513,6 +516,15 @@ inproceedings{ pettie:minirand,
  address = {Redwood City, CA, USA},
 }
 
+@book{ knuth:sas,
+  author = {Donald E. Knuth},
+  title = {{The Art of Computer Programming, Volume 3 (2nd ed.): Sorting and Searching}},
+  year = {1998},
+  isbn = {978-0-201-89685-5},
+  publisher = {Addison Wesley Longman Publishing Co., Inc.},
+  address = {Redwood City, CA, USA},
+}
+
 @inproceedings{ hagerup:wordram,
  author = {Torben Hagerup},
  title = {{Sorting and Searching on the Word RAM}},
@@ -622,3 +634,447 @@ inproceedings{ pettie:minirand,
   journal={Proceedings of the 2nd Electrotechnical and Computer Science Conference, Portoroz, Slovenia},
   year={1993}
 }
+
+@article{ turan:succinct,
+  title={{Succinct representation of graphs.}},
+  author={Tur\'an, G.},
+  journal={Discrete Applied Mathematics},
+  volume={8},
+  number={3},
+  pages={289--294},
+  year={1984}
+}
+
+@book{ jones:haskell,
+  title={{Haskell 98 Language and Libraries: The Revised Report}},
+  author={Jones, P. and Simon, L.},
+  year={2003},
+  publisher={Cambridge University Press}
+}
+
+@article{ mader:dens,
+  title={{Homomorphieeigenschaften und mittlere Kantendichte von Graphen}},
+  author={Mader, W.},
+  journal={Mathematische Annalen},
+  volume={174},
+  number={4},
+  pages={265--268},
+  year={1967},
+  publisher={Springer},
+  note={German}
+}
+
+@inproceedings{ gustedt:parallel,
+    author = "Jens Gustedt",
+    title = "Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel",
+    booktitle = "Symposium on Theoretical Aspects of Computer Science",
+    pages = "421-431",
+    year = "1998",
+    url = "citeseer.ist.psu.edu/223918.html"
+}
+
+@article{ myrvold:rank,
+  title={{Ranking and unranking permutations in linear time}},
+  author={Myrvold, W.J. and Ruskey, F.},
+  journal={Information Processing Letters},
+  volume={79},
+  number={6},
+  pages={281--284},
+  year={2001}
+}
+
+@inproceedings{ critani:rau,
+  title={{Ranking and unranking permutations with applications}},
+  author={Critani, F. and Dall'Aglio, M. and Di Biase, G.},
+  booktitle={Innovation in Mathematics: Proceedings of Second International Mathematica Symposium},
+  pages = "99-106",
+  year = "1997"
+}
+
+@article{ ruskey:ham,
+  title={{The Hamiltonicity of directed-Cayley graphs (or: A tale of backtracking)}},
+  author={Ruskey, F. and Jiang, M. and Weston, A.},
+  journal={Discrete Appl. Math},
+  volume={57},
+  pages={75--83},
+  year={1995}
+}
+
+@article{ ruskey:hce,
+  title={{Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of Sn}},
+  author={Ruskey, F. and Savage, C.D.},
+  journal={SIAM Journal on Discrete Mathematics},
+  volume={6},
+  number={1},
+  pages={152--166},
+  year={1993}
+}
+
+@article{ liehe:raulow,
+  title={{Ranking and Unranking of Lexicographically Ordered Words: An Average-Case Analysis}},
+  author={Liebehenschel, J.},
+  journal={Journal of Automata, Languages and Combinatorics},
+  volume={2},
+  number={4},
+  pages={227--268},
+  year={1997}
+}
+
+@book{ reingold:catp,
+  title={{Combinatorial Algorithms: Theory and Practice}},
+  author={Reingold, E.M.},
+  year={1977},
+  publisher={Prentice Hall College Div}
+}
+
+@inproceedings{ dietz:oal,
+ author = {Paul F. Dietz},
+ title = {Optimal Algorithms for List Indexing and Subset Rank},
+ booktitle = {WADS '89: Proceedings of the Workshop on Algorithms and Data Structures},
+ year = {1989},
+ isbn = {3-540-51542-9},
+ pages = {39--46},
+ publisher = {Springer-Verlag},
+ address = {London, UK},
+}
+
+@book { ss:fifteen,
+  title={{The 15 Puzzle Book}},
+  author={Slocum, J. and Sonneveld D.},
+  year={2006},
+  publisher={The Slocum Puzzle Foundation, Beverly Hills, CA, USA}
+}
+
+@article{ rs:wagner,
+  title={{Graph minors: XX. Wagner's Conjecture}},
+  author={Robertson, N. and Seymour, P. D.},
+  journal={Journal of Combinatorial Theory Series B},
+  volume={92},
+  number={2},
+  pages={325--357},
+  year={2004},
+  publisher={Academic Press, Inc. Orlando, FL, USA}
+}
+
+@book{ matnes:idm,
+  title={{Invitation to Discrete Mathematics}},
+  author={Matou{\v{s}}ek, J. and Ne{\v{s}}et{\v{r}}il, J.},
+  year={1998},
+  publisher={Oxford University Press}
+}
+
+@article{ stanley:econe,
+  title={{Enumerative combinatorics. Vol. 1}},
+  author={Stanley, R.P.},
+  journal={Cambridge Studies in Advanced Mathematics},
+  volume={49},
+  year={1997}
+}
+
+@article{ kaplansky:rooks,
+  title={{The problem of the rooks and its applications}},
+  author={Kaplansky, I. and Riordan, J.},
+  journal={Duke Math. J},
+  volume={13},
+  number={2},
+  pages={259--268},
+  year={1946}
+}
+
+@article{ dinic:flow,
+  author = {E. A. Dinic},
+  title = {Algorithm for solution of a problem of maximum flow in networks with power estimation},
+  journal = {Soviet Math. Dokl.},
+  volume = {11},
+  year = {1970},
+  pages = {1277--1280}
+}
+
+@article{ even:dinic,
+  author = {Shimon Even and Robert Endre Tarjan},
+  title = {Network Flow and Testing Graph Connectivity},
+  publisher = {SIAM},
+  year = {1975},
+  journal = {SIAM Journal on Computing},
+  volume = {4},
+  number = {4},
+  pages = {507--518},
+  url = {http://link.aip.org/link/?SMJ/4/507/1},
+  doi = {10.1137/0204043}
+}
+
+@article{ valiant:permanent,
+  title={{The complexity of computing the permanent}},
+  author={Valiant, L. G.},
+  journal={Theoretical Computer Science},
+  volume={8},
+  number={2},
+  pages={189--201},
+  year={1979}
+}
+
+@article{ jerrum:permanent,
+  title={{A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries}},
+  author={Jerrum, M. and Sinclair, A. and Vigoda, E.},
+  journal={Journal of the ACM},
+  volume={51},
+  number={4},
+  pages={671--697},
+  year={2004}
+}
+
+@article{ kasteleyn:crystals,
+  title={{Graph theory and crystal physics}},
+  author={Kasteleyn, P. W.},
+  journal={Graph Theory and Theoretical Physics},
+  publisher={Academic Press, London},
+  pages={43--110},
+  year={1967}
+}
+
+@article{ yuster:matching,
+  title={{Maximum matching in graphs with an excluded minor}},
+  author={Yuster, R. and Zwick, U.},
+  journal={Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms},
+  pages={108--117},
+  year={2007},
+  publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
+}
+
+@article{ mucha:matching,
+  title={{Maximum Matchings in Planar Graphs via Gaussian Elimination}},
+  author={Mucha, M. and Sankowski, P.},
+  journal={Algorithmica},
+  volume={45},
+  number={1},
+  pages={3--20},
+  year={2006},
+  publisher={Springer}
+}
+
+@article {lovasz:minors,
+  title={{Graph Minor Theory}},
+  author={Lov\'asz, L.},
+  journal={Bulletin of the American Mathematical Society},
+  volume={43},
+  number={1},
+  pages={75--86},
+  year={2005}
+}
+
+@article{ andersson:fusion,
+  title={{Fusion trees can be implemented with AC0 instructions only}},
+  author={Andersson, A. and Miltersen, P.B. and Thorup, M.},
+  journal={Theoretical Computer Science},
+  volume={215},
+  number={1-2},
+  pages={337--344},
+  year={1999},
+  publisher={Elsevier}
+}
+
+@article{ thorup:rampq,
+  title={{On RAM priority queues}},
+  author={THORUP, M.},
+  journal={SIAM journal on computing(Print)},
+  volume={30},
+  number={1},
+  pages={86--109},
+  year={2001},
+  publisher={Society for Industrial and Applied Mathematics}
+}
+
+@article{ thorup:pqsssp,
+  title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
+  author={Thorup, M.},
+  journal={Proceedings of the thirty-fifth ACM Symposium on Theory of Computing},
+  pages={149--158},
+  year={2003},
+  publisher={ACM Press New York, NY, USA}
+}
+
+@article{ chazelle:mstapprox,
+  title={{Approximating the Minimum Spanning Tree Weight in Sublinear Time}},
+  author={Chazelle, B. and Rubinfeld, R. and Trevisan, L.},
+  journal={SIAM Journal on Computing},
+  volume={34},
+  pages={1370},
+  year={2005},
+  publisher={SIAM}
+}
+
+@inproceedings{ czumaj:metric,
+ author = {Artur Czumaj and Christian Sohler},
+ title = {Estimating the weight of metric minimum spanning trees in sublinear-time},
+ booktitle = {STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing},
+ year = {2004},
+ isbn = {1-58113-852-0},
+ pages = {175--183},
+ location = {Chicago, IL, USA},
+ doi = {http://doi.acm.org/10.1145/1007352.1007386},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+}
+
+@inproceedings{ czumaj:euclidean,
+ author = {Artur Czumaj and Funda Erg\"{u}n and Lance Fortnow and Avner Magen and Ilan Newman and Ronitt Rubinfeld and Christian Sohler},
+ title = {Sublinear-time approximation of Euclidean minimum spanning tree},
+ booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
+ year = {2003},
+ isbn = {0-89871-538-5},
+ pages = {813--822},
+ location = {Baltimore, Maryland},
+ publisher = {Society for Industrial and Applied Mathematics},
+ address = {Philadelphia, PA, USA},
+}
+
+@book{ ieee:binfp,
+  author = {IEEE},
+  title = {IEEE Standard 754-1985 for Binary Floating-point Arithmetic},
+  year = {1985},
+  publisher = {IEEE}
+}
+
+@article{ dgoldberg:fp,
+  title={{What every computer scientist should know about floating-point arithmetic}},
+  author={Goldberg, D.},
+  journal={ACM Computing Surveys (CSUR)},
+  volume={23},
+  number={1},
+  pages={5--48},
+  year={1991},
+  publisher={ACM Press New York, NY, USA}
+}
+
+@article{ thorup:floatint,
+  title={{Floats, Integers, and Single Source Shortest Paths}},
+  author={Thorup, M.},
+  journal={Journal of Algorithms},
+  volume={35},
+  number={2},
+  pages={189--201},
+  year={2000},
+  publisher={Academic Press}
+}
+
+@article{ shamos:closest,
+  title={{Closest-point problems}},
+  author={Shamos, M. I. and Hoey, D.},
+  journal={Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science},
+  pages={151--162},
+  year={1975}
+}
+
+@article{ fortune:voronoi,
+  title={{A sweepline algorithm for Voronoi diagrams}},
+  author={Fortune, S.},
+  journal={Algorithmica},
+  volume={2},
+  number={1},
+  pages={153--174},
+  year={1987},
+  publisher={Springer}
+}
+
+@article{ zhou:nodel,
+  title={{Efficient minimum spanning tree construction without Delaunay triangulation}},
+  author={Zhou, H. and Shenoy, N. and Nicholls, W.},
+  journal={Information Processing Letters},
+  volume={81},
+  number={5},
+  pages={271--276},
+  year={2002},
+  publisher={Elsevier}
+}
+
+@techreport{ eppstein:spanning,
+  title={{Spanning Trees and Spanners}},
+  author={Eppstein, D.},
+  year={1996},
+  institution={Information and Computer Science, University of California, Irvine}
+}
+
+@article{ garey:steiner,
+  title={{The Complexity of Computing Steiner Minimal Trees}},
+  author={Garey, M.R. and Graham, R.L. and Johnson, D.S.},
+  journal={SIAM Journal on Applied Mathematics},
+  volume={32},
+  number={4},
+  pages={835--859},
+  year={1977},
+}
+
+@article{ garey:rectisteiner,
+  title={{The Rectilinear Steiner Tree Problem is NP-Complete}},
+  author={Garey, M.R. and Johnson, D.S.},
+  journal={SIAM Journal on Applied Mathematics},
+  volume={32},
+  number={4},
+  pages={826--834},
+  year={1977},
+}
+
+@article{ proemel:steiner,
+  title={{A new approximation algorithm for the Steiner tree problem with performance ratio $5/3$}},
+  author={Promel, H.J. and Steger, A.},
+  journal={Journal of Algorithms},
+  volume={36},
+  pages={89--101},
+  year={2000}
+}
+
+@article{ arora:tspapx,
+  title={{Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems}},
+  author={Arora, S.},
+  journal={Journal of the ACM (JACM)},
+  volume={45},
+  number={5},
+  pages={753--782},
+  year={1998},
+  publisher={ACM Press New York, NY, USA}
+}
+
+@article{ harel:nca,
+  title={{Fast algorithms for finding nearest common ancestors}},
+  author={Harel, D. and Tarjan, R.E.},
+  journal={SIAM Journal on Computing},
+  volume={13},
+  number={2},
+  pages={338--355},
+  year={1984},
+  publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
+}
+
+@article{ gomoryhu,
+   author = "R. E. Gomory and T. C. Hu",
+   title = "Multi-Terminal Network Flows",
+   journal = "{Journal of SIAM}",
+   volume = {9},
+   number = {4},
+   year = {1961},
+   pages = {551--570}
+}
+
+@inproceedings{ bhalgat:ght,
+ author = {Ramesh Hariharan and Telikepalli Kavitha and Debmalya Panigrahi and Anand Bhalgat},
+ title = {{An $\widehat\O(mn)$ Gomory-Hu tree construction algorithm for unweighted graphs}},
+ booktitle = {STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing},
+ year = {2007},
+ isbn = {978-1-59593-631-8},
+ pages = {605--614},
+ location = {San Diego, California, USA},
+ doi = {http://doi.acm.org/10.1145/1250790.1250879},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+}
+
+@article{ sleator:trees,
+  title={{A data structure for dynamic trees}},
+  author={Sleator, D.D. and Tarjan, R.E.},
+  journal={Journal of Computer and System Sciences},
+  volume={26},
+  number={3},
+  pages={362--391},
+  year={1983},
+  publisher={Academic Press, Inc. Orlando, FL, USA}
+}