Minimizing diameters of dynamic trees. (English) Zbl 1401.68240
Degano, Pierpaolo (ed.) et al., Automata, languages and programming. 24th international colloquium, ICALP ’97, Bologna, Italy, July 7–11, 1997. Proceedings. Berlin: Springer-Verlag (ISBN 978-3-540-63165-1/pbk; 978-3-540-69194-5/ebook). Lecture Notes in Computer Science 1256, 270-280 (1997).
Summary: In this paper we consider an on-line problem related to minimizing the diameter of a dynamic tree \(T\). A new edge \(f\) is added, and our task is to delete the edge \(e\) of the induced cycle so as to minimize the diameter of the resulting tree \(T\cup \{f\}\backslash\{e\}\). Starting with a tree with \(n\) nodes, we show how each such best swap can be found in worst-case \(O(\log^2n)\) time. The problem was raised by G. F. Italiano and R. Ramaswami [Algorithmica 22, No. 3, 275–304 (1998; Zbl 0915.68084)] together with a related problem for edge deletions. Italiano and Ramaswami [loc. cit.] solved both problems in \(O(n)\) time per operation.
For the entire collection see [Zbl 1369.68020].
For the entire collection see [Zbl 1369.68020].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68Q25 | Analysis of algorithms and problem complexity |
Citations:
Zbl 0915.68084References:
| [1] | 1.Z-Z. Chen. A simple parallel algorithm for computing the diameters of all vertices in a tree and its application. \(Information Processing Letters\), 42:243-248, 1992. · Zbl 0764.68047 · doi:10.1016/0020-0190(92)90031-P |
| [2] | 2.G. N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. \(SIAM J. Computing\), 14(4):781-798, 1985. · Zbl 0575.68068 |
| [3] | 3.G. N. Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. In \(IEEE Symposium on Foundations of Computer Science (FOCS)\), pages 632-641, 1991. |
| [4] | 4.G.Y. Handler. Minimax location of a facility in an undirected tree network. \(Transportation. Sci.\), 7:287-293, 1973. |
| [5] | 5.G. F. Italiano and R. Ramaswami. Mantaining spanning trees of small diameter. In \(Proc. 21st Int. Coll. on Automata, Languages and Programming\). Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1994. · Zbl 0915.68084 |
| [6] | 6.G. F. Italiano and R. Ramaswami. Mantaining spanning trees of small diameter. Unpublished revised version of the ICALP paper, 1996. |
| [7] | 7.R. Ramaswami. Multi-wavelength lightwave networks for computer communication. \(IEEE Communications Magazine\), 31:78-88, 1993. · doi:10.1109/35.186364 |
| [8] | 8.M. Rauch. \(Fully dynamic graph algorithms and their data structures\). PhD thesis, Department of computer science, Princeton University, December 1992. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
