From 1bcd89eb4ae54a284a07aa6544f9a97fce85cb27 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Wed, 19 Mar 2008 21:20:02 +0100
Subject: [PATCH] Updated bibliography.

---
 PLAN       |  2 +-
 biblio.bib | 36 ++++++++++++++++++++++++++++++++++--
 2 files changed, 35 insertions(+), 3 deletions(-)

diff --git a/PLAN b/PLAN
index 20a4c0d..42c81f2 100644
--- a/PLAN
+++ b/PLAN
@@ -55,7 +55,7 @@ Spanning trees:
 - reference to mixed Boruvka-Jarnik
 - use the notation for contraction by a set
 - practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
-- parallel algorithms: p243-cole (see also remarks in Karger and pettie:minirand)
+- parallel algorithms: p243-cole (see also remarks in Karger and pettie:minirand), pettie:parallel
 - bounded expansion classes?
 - restricted cases and arborescences
 - Pettie's paper on random bits (pettie:minirand)
diff --git a/biblio.bib b/biblio.bib
index 01aca86..4fb17c0 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -160,7 +160,17 @@
     type = "Tech Report"
 }
 
-@inproceedings { pettie:optimal,
+@article{ pettie:optimal,
+ author = {Seth Pettie and Vijaya Ramachandran},
+ title= {An optimal minimum spanning tree algorithm},
+ journal = {Journal of the {ACM}},
+ volume = {49},
+ number = {1},
+ year = {2002},
+ pages = {16--34},
+}
+
+@inproceedings { pettie:optimal-conf,
    author = "Seth Pettie and Vijaya Ramachandran",
    title = "{An Optimal Minimum Spanning Tree Algorithm}",
    booktitle = "{Proceedings of ICALP'2000}",
@@ -416,7 +426,18 @@
   publisher={McGraw-Hill}
 }
 
-@inproceedings{ pettie:onlineverify,
+@article{ pettie:onlineverify,
+ author       = {Seth Pettie},
+ title        = {An Inverse-{A}ckermann Type Lower Bound for Online
+                 Minimum Spanning Tree Verification},
+ journal      = {Combinatorica},
+ volume       = {26},
+ number       = {2},
+ pages        = {207--230},
+ year         = {2006},
+}
+
+@inproceedings{ pettie:onlineverify-conf,
   author = "S. Pettie",
   title = "An inverse-{A}ckermann style lower bound for the online minimum spanning
     tree verification problem",
@@ -1109,3 +1130,14 @@ inproceedings{ pettie:minirand,
   year={1952},
   publisher={JSTOR}
 }
+
+@article{ pettie:parallel,
+ author       = {Seth Pettie and Vijaya Ramachandran},
+ title        = {A randomized time-work optimal parallel algorithm for
+                 finding a minimum spanning forest},
+ journal      = {SIAM J. Comput.},
+ volume       = {31},
+ number       = {6},
+ year         = {2002},
+ pages        = {1879--1895},
+}
-- 
2.39.2