[{"abstract":[{"lang":"eng","text":"We present the first fully dynamic algorithm for maintaining a minimum spanning tree in time o(√n) per operation. To be precise, the algorithm uses O(n 1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and, bipartiteness in amortized time O(n 1/3 log n) per update, with O(1) worst case time per query."}],"doi":"10.1007/3-540-63165-8_214","day":"01","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["9783540691945"],"isbn":["9783540631651"]},"date_published":"1997-07-01T00:00:00Z","type":"conference","date_updated":"2023-02-14T07:49:03Z","citation":{"ista":"Henzinger MH, King V. 1997. Maintaining minimum spanning trees in dynamic graphs. 24th International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 1256, 594–604.","mla":"Henzinger, Monika H., and Valerie King. “Maintaining Minimum Spanning Trees in Dynamic Graphs.” <i>24th International Colloquium on Automata, Languages and Programming</i>, vol. 1256, Springer Nature, 1997, pp. 594–604, doi:<a href=\"https://doi.org/10.1007/3-540-63165-8_214\">10.1007/3-540-63165-8_214</a>.","short":"M.H. Henzinger, V. King, in:, 24th International Colloquium on Automata, Languages and Programming, Springer Nature, 1997, pp. 594–604.","chicago":"Henzinger, Monika H, and Valerie King. “Maintaining Minimum Spanning Trees in Dynamic Graphs.” In <i>24th International Colloquium on Automata, Languages and Programming</i>, 1256:594–604. Springer Nature, 1997. <a href=\"https://doi.org/10.1007/3-540-63165-8_214\">https://doi.org/10.1007/3-540-63165-8_214</a>.","ieee":"M. H. Henzinger and V. King, “Maintaining minimum spanning trees in dynamic graphs,” in <i>24th International Colloquium on Automata, Languages and Programming</i>, Bologna, Italy, 1997, vol. 1256, pp. 594–604.","ama":"Henzinger MH, King V. Maintaining minimum spanning trees in dynamic graphs. In: <i>24th International Colloquium on Automata, Languages and Programming</i>. Vol 1256. Springer Nature; 1997:594–604. doi:<a href=\"https://doi.org/10.1007/3-540-63165-8_214\">10.1007/3-540-63165-8_214</a>","apa":"Henzinger, M. H., &#38; King, V. (1997). Maintaining minimum spanning trees in dynamic graphs. In <i>24th International Colloquium on Automata, Languages and Programming</i> (Vol. 1256, pp. 594–604). Bologna, Italy: Springer Nature. <a href=\"https://doi.org/10.1007/3-540-63165-8_214\">https://doi.org/10.1007/3-540-63165-8_214</a>"},"year":"1997","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","volume":1256,"alternative_title":["LNCS"],"month":"07","title":"Maintaining minimum spanning trees in dynamic graphs","intvolume":"      1256","publication_status":"published","oa_version":"None","article_processing_charge":"No","date_created":"2022-08-11T13:35:06Z","author":[{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"King, Valerie","first_name":"Valerie","last_name":"King"}],"publication":"24th International Colloquium on Automata, Languages and Programming","_id":"11803","scopus_import":"1","conference":{"end_date":"1997-07-11","location":"Bologna, Italy","name":"ICALP: International Colloquium on Automata, Languages, and Programming","start_date":"1997-07-07"},"publisher":"Springer Nature","language":[{"iso":"eng"}],"page":"594–604","quality_controlled":"1"},{"day":"01","doi":"10.1007/3-540-63165-8_213","abstract":[{"text":"Rectangular hybrid automata model digital control programs of analog plant environments. We study rectangular hybrid automata where the plant state evolves continuously in real-numbered time, and the controller samples the plant state and changes the control state discretely, only at the integer points in time. We prove that rectangular hybrid automata have finite bisimilarity quotients when all control transitions happen at integer times, even if the constraints on the derivatives of the variables vary between control states. This is sharply in contrast with the conventional model where control transitions may happen at any real time, and already the reachability problem is undecidable. Based on the finite bisimilarity quotients, we give an exponential algorithm for the symbolic sampling-controller synthesis of rectangular automata. We show our algorithm to be optimal by proving the problem to be EXPTIME-hard. We also show that rectangular automata form a maximal class of systems for which the sampling-controller synthesis problem can be solved algorithmically.","lang":"eng"}],"year":"1997","citation":{"ama":"Henzinger TA, Kopke P. Discrete-time control for rectangular hybrid automata. In: <i>Proceedings of the 24th International Colloquium on Automata, Languages and Programming</i>. Vol 1256. Springer; 1997:582-593. doi:<a href=\"https://doi.org/10.1007/3-540-63165-8_213\">10.1007/3-540-63165-8_213</a>","apa":"Henzinger, T. A., &#38; Kopke, P. (1997). Discrete-time control for rectangular hybrid automata. In <i>Proceedings of the 24th International Colloquium on Automata, Languages and Programming</i> (Vol. 1256, pp. 582–593). Bologna, Italy: Springer. <a href=\"https://doi.org/10.1007/3-540-63165-8_213\">https://doi.org/10.1007/3-540-63165-8_213</a>","ieee":"T. A. Henzinger and P. Kopke, “Discrete-time control for rectangular hybrid automata,” in <i>Proceedings of the 24th International Colloquium on Automata, Languages and Programming</i>, Bologna, Italy, 1997, vol. 1256, pp. 582–593.","chicago":"Henzinger, Thomas A, and Peter Kopke. “Discrete-Time Control for Rectangular Hybrid Automata.” In <i>Proceedings of the 24th International Colloquium on Automata, Languages and Programming</i>, 1256:582–93. Springer, 1997. <a href=\"https://doi.org/10.1007/3-540-63165-8_213\">https://doi.org/10.1007/3-540-63165-8_213</a>.","mla":"Henzinger, Thomas A., and Peter Kopke. “Discrete-Time Control for Rectangular Hybrid Automata.” <i>Proceedings of the 24th International Colloquium on Automata, Languages and Programming</i>, vol. 1256, Springer, 1997, pp. 582–93, doi:<a href=\"https://doi.org/10.1007/3-540-63165-8_213\">10.1007/3-540-63165-8_213</a>.","short":"T.A. Henzinger, P. Kopke, in:, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, Springer, 1997, pp. 582–593.","ista":"Henzinger TA, Kopke P. 1997. Discrete-time control for rectangular hybrid automata. Proceedings of the 24th International Colloquium on Automata, Languages and Programming. ICALP: Automata, Languages and Programming, LNCS, vol. 1256, 582–593."},"date_updated":"2022-08-17T12:04:15Z","acknowledgement":"This research was supported in part by the ONR YIP award N00014-95-1-0520, by the NSF CAREER award CCR-9501708, by the NSF grant CCR-9504469, by the AFOSR contract F49620-93-1-0056, by the ARO MURI contract DAAH-04-96-1-0341, by the ARO contract DAAL03-91-C-0027 through the MSI at Cornell University, by the ARPA grant NAG2-892, and by the SRC contract 95-DC-324.036.","volume":1256,"extern":"1","date_created":"2018-12-11T12:08:52Z","article_processing_charge":"No","publication_status":"published","intvolume":"      1256","title":"Discrete-time control for rectangular hybrid automata","alternative_title":["LNCS"],"scopus_import":"1","_id":"4441","author":[{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kopke, Peter","last_name":"Kopke","first_name":"Peter"}],"publisher":"Springer","quality_controlled":"1","page":"582 - 593","publication_identifier":{"isbn":["9783540631651"]},"publist_id":"289","type":"conference","date_published":"1997-01-01T00:00:00Z","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","month":"01","publication":"Proceedings of the 24th International Colloquium on Automata, Languages and Programming","conference":{"end_date":"1997-07-11","location":"Bologna, Italy","name":"ICALP: Automata, Languages and Programming","start_date":"1997-07-07"},"language":[{"iso":"eng"}]}]