---
_id: '11803'
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.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Valerie
full_name: King, Valerie
last_name: King
citation:
ama: 'Henzinger MH, King V. Maintaining minimum spanning trees in dynamic graphs.
In: 24th International Colloquium on Automata, Languages and Programming.
Vol 1256. Springer Nature; 1997:594–604. doi:10.1007/3-540-63165-8_214'
apa: 'Henzinger, M. H., & King, V. (1997). Maintaining minimum spanning trees
in dynamic graphs. In 24th International Colloquium on Automata, Languages
and Programming (Vol. 1256, pp. 594–604). Bologna, Italy: Springer Nature.
https://doi.org/10.1007/3-540-63165-8_214'
chicago: Henzinger, Monika H, and Valerie King. “Maintaining Minimum Spanning Trees
in Dynamic Graphs.” In 24th International Colloquium on Automata, Languages
and Programming, 1256:594–604. Springer Nature, 1997. https://doi.org/10.1007/3-540-63165-8_214.
ieee: M. H. Henzinger and V. King, “Maintaining minimum spanning trees in dynamic
graphs,” in 24th International Colloquium on Automata, Languages and Programming,
Bologna, Italy, 1997, vol. 1256, pp. 594–604.
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.” 24th International Colloquium on Automata, Languages and
Programming, vol. 1256, Springer Nature, 1997, pp. 594–604, doi:10.1007/3-540-63165-8_214.
short: M.H. Henzinger, V. King, in:, 24th International Colloquium on Automata,
Languages and Programming, Springer Nature, 1997, pp. 594–604.
conference:
end_date: 1997-07-11
location: Bologna, Italy
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 1997-07-07
date_created: 2022-08-11T13:35:06Z
date_published: 1997-07-01T00:00:00Z
date_updated: 2023-02-14T07:49:03Z
day: '01'
doi: 10.1007/3-540-63165-8_214
extern: '1'
intvolume: ' 1256'
language:
- iso: eng
month: '07'
oa_version: None
page: 594–604
publication: 24th International Colloquium on Automata, Languages and Programming
publication_identifier:
eisbn:
- '9783540691945'
eissn:
- 1611-3349
isbn:
- '9783540631651'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Maintaining minimum spanning trees in dynamic graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1256
year: '1997'
...
---
_id: '4441'
abstract:
- lang: eng
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.
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.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Peter
full_name: Kopke, Peter
last_name: Kopke
citation:
ama: 'Henzinger TA, Kopke P. Discrete-time control for rectangular hybrid automata.
In: Proceedings of the 24th International Colloquium on Automata, Languages
and Programming. Vol 1256. Springer; 1997:582-593. doi:10.1007/3-540-63165-8_213'
apa: 'Henzinger, T. A., & Kopke, P. (1997). Discrete-time control for rectangular
hybrid automata. In Proceedings of the 24th International Colloquium on Automata,
Languages and Programming (Vol. 1256, pp. 582–593). Bologna, Italy: Springer.
https://doi.org/10.1007/3-540-63165-8_213'
chicago: Henzinger, Thomas A, and Peter Kopke. “Discrete-Time Control for Rectangular
Hybrid Automata.” In Proceedings of the 24th International Colloquium on Automata,
Languages and Programming, 1256:582–93. Springer, 1997. https://doi.org/10.1007/3-540-63165-8_213.
ieee: T. A. Henzinger and P. Kopke, “Discrete-time control for rectangular hybrid
automata,” in Proceedings of the 24th International Colloquium on Automata,
Languages and Programming, Bologna, Italy, 1997, vol. 1256, 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.'
mla: Henzinger, Thomas A., and Peter Kopke. “Discrete-Time Control for Rectangular
Hybrid Automata.” Proceedings of the 24th International Colloquium on Automata,
Languages and Programming, vol. 1256, Springer, 1997, pp. 582–93, doi:10.1007/3-540-63165-8_213.
short: T.A. Henzinger, P. Kopke, in:, Proceedings of the 24th International Colloquium
on Automata, Languages and Programming, Springer, 1997, pp. 582–593.
conference:
end_date: 1997-07-11
location: Bologna, Italy
name: 'ICALP: Automata, Languages and Programming'
start_date: 1997-07-07
date_created: 2018-12-11T12:08:52Z
date_published: 1997-01-01T00:00:00Z
date_updated: 2022-08-17T12:04:15Z
day: '01'
doi: 10.1007/3-540-63165-8_213
extern: '1'
intvolume: ' 1256'
language:
- iso: eng
month: '01'
oa_version: None
page: 582 - 593
publication: Proceedings of the 24th International Colloquium on Automata, Languages
and Programming
publication_identifier:
isbn:
- '9783540631651'
publication_status: published
publisher: Springer
publist_id: '289'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Discrete-time control for rectangular hybrid automata
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1256
year: '1997'
...