×
Author ID: king.valerie Recent zbMATH articles by "King, Valerie"
Published as: King, Valerie; King, V.
External Links: MGP · Wikidata · dblp

Publications by Year

Citations contained in zbMATH Open

48 Publications have been cited 364 times in 267 Documents Cited by Year
A faster deterministic maximum flow algorithm. Zbl 1321.05269
King, V.; Rao, S.; Tarjan, R.
31
1994
Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Zbl 1065.68665
Henzinger, Monika R.; King, Valerie
29
1999
Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Zbl 0936.68026
Henzinger, M. R.; King, V.; Warnow, T.
24
1999
Dynamic graph connectivity in polylogarithmic worst case time. Zbl 1423.68345
Kapron, Bruce M.; King, Valerie; Mountjoy, Ben
24
2013
Scalable leader election. Zbl 1192.91082
King, Valerie; Saia, Jared; Sanwalani, Vishal; Vee Erik
24
2006
Fully dynamic biconnectivity and transitive closure. Zbl 0938.68919
Rauch Henzinger, Monika; King, Valerie
21
1995
On the complexity of distance-based evolutionary tree reconstruction. Zbl 1094.68614
King, Valerie; Zhang, Li; Zhou, Yunhong
18
2003
Randomized dynamic graph algorithms with polylogarithmic time per operation. Zbl 0978.68556
Rauch Henzinger, Monika; King, Valerie
17
1995
Maintaining minimum spanning forests in dynamic graphs. Zbl 0996.68129
Henzinger, Monika R.; King, Valerie
11
2001
A simpler minimum spanning tree verification algorithm. Zbl 0868.68061
King, V.
10
1997
Breaking the \(O(n^2)\) bit barrier, scalable Byzantine agreement with an adaptive adversary. Zbl 1315.68272
King, Valerie; Saia, Jared
10
2010
From almost everywhere to everywhere: Byzantine agreement with \(\tilde{O}(n^{3/2})\) bits. Zbl 1261.68167
King, Valerie; Saia, Jared
9
2009
Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication. Zbl 1333.68213
King, Valerie; Kutten, Shay; Thorup, Mikkel
9
2015
Maintaining minimum spanning trees in dynamic graphs. Zbl 1401.68249
Henzinger, Monika R.; King, Valerie
9
1997
On the complexity of parity word automata. Zbl 0978.68077
King, Valerie; Kupferman, Orna; Vardi, Moshe Y.
8
2001
A fully dynamic algorithm for maintaining the transitive closure. Zbl 1020.68106
King, Valerie; Sagert, Garry
8
2002
Conflict on a communication channel. Zbl 1321.68027
King, Valerie; Saia, Jared; Young, Maxwell
8
2011
Breaking the \(O(n^2)\) bit barrier, scalable Byzantine agreement with an adaptive adversary. Zbl 1281.68047
King, Valerie; Saia, Jared
8
2011
A faster deterministic maximum flow algorithm. Zbl 0829.68094
King, V.; Rao, S.; Tarjan, R.
7
1992
Optimal randomized algorithms for local sorting and set-maxima. Zbl 0770.68047
Goddard, Wayne; Kenyon, Claire; King, Valerie; Schulman, Leonard J.
7
1993
Fast asynchronous byzantine agreement and leader election with full information. Zbl 1192.68083
Kapron, Bruce; Kempe, David; King, Valerie; Saia Jared; Sanwalani, Vishal
7
2008
A lower bound for the recognition of digraph properties. Zbl 0733.05041
King, V.
6
1990
On Boolean decision trees with faulty nodes. Zbl 0811.68101
Kenyon, Claire; King, Valerie
6
1994
A simple, faster method for kinetic proximity problems. Zbl 1314.65032
Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue; Zarei, Alireza
6
2015
Choosing a random peer. Zbl 1321.68051
King, Valerie; Saia, Jared
6
2004
A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds. Zbl 1428.68363
Agarwal, Udit; Ramachandran, Vijaya; King, Valerie; Pontecorvi, Matteo
6
2018
Fast asynchronous Byzantine agreement and leader election with full information. Zbl 1300.68012
Kapron, Bruce M.; Kempe, David; King, Valerie; Saia, Jared; Sanwalani, Vishal
5
2010
Byzantine agreement in expected polynomial time. Zbl 1426.68024
King, Valerie; Saia, Jared
5
2016
Brief announcement: Breaking the \(O(nm)\) bit barrier, secure multiparty computation with a static adversary. Zbl 1301.68251
Dani, Varsha; King, Valerie; Movahedi, Mahnush; Saia, Jared
5
2012
Limits on the power of parallel random access machines with weak forms of write conflict resolution. Zbl 0842.68033
Fich, Faith E.; Impagliazzo, Russell; Kapron, Bruce; King, Valerie; Kutylowski, Miroslaw
4
1993
Secure multi-party computation in large networks. Zbl 1409.68041
Dani, Varsha; King, Valerie; Movahedi, Mahnush; Saia, Jared; Zamani, Mahdi
4
2017
Byzantine agreement in polynomial expected time (extended abstract). Zbl 1293.68056
King, Valerie; Saia, Jared
3
2013
An optimal EREW PRAM algorithm for minimum spanning tree verification. Zbl 1337.68285
King, Valerie; Poon, Chung Keung; Ramachandran, Vijaya; Sinha, Santanu
3
1997
A space saving trick for directed dynamic transitive closure and shortest path algorithms. Zbl 0996.68526
King, Valerie; Thorup, Mikkel
3
2001
Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Zbl 0848.68077
Rauch Henzinger, Monika; King, Valerie; Warnow, Tandy
2
1996
Sleeping on the job: energy-efficient and robust broadcast for radio networks. Zbl 1225.68050
King, Valerie; Phillips, Cynthia; Saia, Jared; Young, Maxwell
2
2011
Kinetic data structures for all nearest neighbors and closest pair in the plane. Zbl 1305.68070
Rahmati, Zahed; King, Valerie; Whitesides, Sue
2
2013
Sleeping on the job, energy-efficient and robust broadcast for radio networks. Zbl 1301.68036
King, Valerie; Phillips, Cynthia; Saia, Jared; Young, Maxwell
2
2008
A resource-competitive jamming defense. Zbl 1482.68048
King, Valerie; Pettie, Seth; Saia, Jared; Young, Maxwell
2
2018
An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties. Zbl 0743.68077
King, Valerie
1
1991
Kinetic reverse \(k\)-nearest neighbor problem. Zbl 1401.68352
Rahmati, Zahed; King, Valerie; Whitesides, Sue
1
2015
Lower bound for scalable Byzantine agreement. Zbl 1267.68068
Holtby, Dan; Kapron, Bruce M.; King, Valerie
1
2008
A fully dynamic algorithm for maintaining the transitive closure. Zbl 1345.05102
King, Valerie; Sagert, Garry
1
1999
A simpler minimum spanning tree verification algorithm. Zbl 1502.68236
King, Valerie
1
1995
Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model. Zbl 1497.68567
Mashreghi, Ali; King, Valerie
1
2018
Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model. Zbl 1522.68733
Mashreghi, Ali; King, Valerie
1
2021
Kinetic and stationary point-set embeddability for plane graphs. Zbl 1377.68186
Rahmati, Zahed; Whitesides, Sue H.; King, Valerie
1
2013
Kinetic \(k\)-semi-Yao graph and its applications. Zbl 1506.68018
Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue
1
2019
Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model. Zbl 1522.68733
Mashreghi, Ali; King, Valerie
1
2021
Kinetic \(k\)-semi-Yao graph and its applications. Zbl 1506.68018
Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue
1
2019
A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds. Zbl 1428.68363
Agarwal, Udit; Ramachandran, Vijaya; King, Valerie; Pontecorvi, Matteo
6
2018
A resource-competitive jamming defense. Zbl 1482.68048
King, Valerie; Pettie, Seth; Saia, Jared; Young, Maxwell
2
2018
Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model. Zbl 1497.68567
Mashreghi, Ali; King, Valerie
1
2018
Secure multi-party computation in large networks. Zbl 1409.68041
Dani, Varsha; King, Valerie; Movahedi, Mahnush; Saia, Jared; Zamani, Mahdi
4
2017
Byzantine agreement in expected polynomial time. Zbl 1426.68024
King, Valerie; Saia, Jared
5
2016
Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication. Zbl 1333.68213
King, Valerie; Kutten, Shay; Thorup, Mikkel
9
2015
A simple, faster method for kinetic proximity problems. Zbl 1314.65032
Rahmati, Zahed; Abam, Mohammad Ali; King, Valerie; Whitesides, Sue; Zarei, Alireza
6
2015
Kinetic reverse \(k\)-nearest neighbor problem. Zbl 1401.68352
Rahmati, Zahed; King, Valerie; Whitesides, Sue
1
2015
Dynamic graph connectivity in polylogarithmic worst case time. Zbl 1423.68345
Kapron, Bruce M.; King, Valerie; Mountjoy, Ben
24
2013
Byzantine agreement in polynomial expected time (extended abstract). Zbl 1293.68056
King, Valerie; Saia, Jared
3
2013
Kinetic data structures for all nearest neighbors and closest pair in the plane. Zbl 1305.68070
Rahmati, Zahed; King, Valerie; Whitesides, Sue
2
2013
Kinetic and stationary point-set embeddability for plane graphs. Zbl 1377.68186
Rahmati, Zahed; Whitesides, Sue H.; King, Valerie
1
2013
Brief announcement: Breaking the \(O(nm)\) bit barrier, secure multiparty computation with a static adversary. Zbl 1301.68251
Dani, Varsha; King, Valerie; Movahedi, Mahnush; Saia, Jared
5
2012
Conflict on a communication channel. Zbl 1321.68027
King, Valerie; Saia, Jared; Young, Maxwell
8
2011
Breaking the \(O(n^2)\) bit barrier, scalable Byzantine agreement with an adaptive adversary. Zbl 1281.68047
King, Valerie; Saia, Jared
8
2011
Sleeping on the job: energy-efficient and robust broadcast for radio networks. Zbl 1225.68050
King, Valerie; Phillips, Cynthia; Saia, Jared; Young, Maxwell
2
2011
Breaking the \(O(n^2)\) bit barrier, scalable Byzantine agreement with an adaptive adversary. Zbl 1315.68272
King, Valerie; Saia, Jared
10
2010
Fast asynchronous Byzantine agreement and leader election with full information. Zbl 1300.68012
Kapron, Bruce M.; Kempe, David; King, Valerie; Saia, Jared; Sanwalani, Vishal
5
2010
From almost everywhere to everywhere: Byzantine agreement with \(\tilde{O}(n^{3/2})\) bits. Zbl 1261.68167
King, Valerie; Saia, Jared
9
2009
Fast asynchronous byzantine agreement and leader election with full information. Zbl 1192.68083
Kapron, Bruce; Kempe, David; King, Valerie; Saia Jared; Sanwalani, Vishal
7
2008
Sleeping on the job, energy-efficient and robust broadcast for radio networks. Zbl 1301.68036
King, Valerie; Phillips, Cynthia; Saia, Jared; Young, Maxwell
2
2008
Lower bound for scalable Byzantine agreement. Zbl 1267.68068
Holtby, Dan; Kapron, Bruce M.; King, Valerie
1
2008
Scalable leader election. Zbl 1192.91082
King, Valerie; Saia, Jared; Sanwalani, Vishal; Vee Erik
24
2006
Choosing a random peer. Zbl 1321.68051
King, Valerie; Saia, Jared
6
2004
On the complexity of distance-based evolutionary tree reconstruction. Zbl 1094.68614
King, Valerie; Zhang, Li; Zhou, Yunhong
18
2003
A fully dynamic algorithm for maintaining the transitive closure. Zbl 1020.68106
King, Valerie; Sagert, Garry
8
2002
Maintaining minimum spanning forests in dynamic graphs. Zbl 0996.68129
Henzinger, Monika R.; King, Valerie
11
2001
On the complexity of parity word automata. Zbl 0978.68077
King, Valerie; Kupferman, Orna; Vardi, Moshe Y.
8
2001
A space saving trick for directed dynamic transitive closure and shortest path algorithms. Zbl 0996.68526
King, Valerie; Thorup, Mikkel
3
2001
Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Zbl 1065.68665
Henzinger, Monika R.; King, Valerie
29
1999
Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Zbl 0936.68026
Henzinger, M. R.; King, V.; Warnow, T.
24
1999
A fully dynamic algorithm for maintaining the transitive closure. Zbl 1345.05102
King, Valerie; Sagert, Garry
1
1999
A simpler minimum spanning tree verification algorithm. Zbl 0868.68061
King, V.
10
1997
Maintaining minimum spanning trees in dynamic graphs. Zbl 1401.68249
Henzinger, Monika R.; King, Valerie
9
1997
An optimal EREW PRAM algorithm for minimum spanning tree verification. Zbl 1337.68285
King, Valerie; Poon, Chung Keung; Ramachandran, Vijaya; Sinha, Santanu
3
1997
Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Zbl 0848.68077
Rauch Henzinger, Monika; King, Valerie; Warnow, Tandy
2
1996
Fully dynamic biconnectivity and transitive closure. Zbl 0938.68919
Rauch Henzinger, Monika; King, Valerie
21
1995
Randomized dynamic graph algorithms with polylogarithmic time per operation. Zbl 0978.68556
Rauch Henzinger, Monika; King, Valerie
17
1995
A simpler minimum spanning tree verification algorithm. Zbl 1502.68236
King, Valerie
1
1995
A faster deterministic maximum flow algorithm. Zbl 1321.05269
King, V.; Rao, S.; Tarjan, R.
31
1994
On Boolean decision trees with faulty nodes. Zbl 0811.68101
Kenyon, Claire; King, Valerie
6
1994
Optimal randomized algorithms for local sorting and set-maxima. Zbl 0770.68047
Goddard, Wayne; Kenyon, Claire; King, Valerie; Schulman, Leonard J.
7
1993
Limits on the power of parallel random access machines with weak forms of write conflict resolution. Zbl 0842.68033
Fich, Faith E.; Impagliazzo, Russell; Kapron, Bruce; King, Valerie; Kutylowski, Miroslaw
4
1993
A faster deterministic maximum flow algorithm. Zbl 0829.68094
King, V.; Rao, S.; Tarjan, R.
7
1992
An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties. Zbl 0743.68077
King, Valerie
1
1991
A lower bound for the recognition of digraph properties. Zbl 0733.05041
King, V.
6
1990
all top 5

Cited by 531 Authors

13 King, Valerie
12 Rauch Henzinger, Monika
9 Saia, Jared
7 Italiano, Giuseppe Francesco
7 Jansson, Jesper
6 Baswana, Surender
6 Rahmati, Zahed
6 Young, Maxwell
5 Hellmuth, Marc
5 Roch, Sébastien
5 Roditty, Liam
4 Augustine, John E.
4 Censor-Hillel, Keren
4 Chatterjee, Krishnendu
4 Cohen, Ran
4 Demetrescu, Camil
4 Karczmarz, Adam
4 Krinninger, Sebastian
4 Movahedi, Mahnush
4 Nanongkai, Danupon
4 Paschos, Vangelis Th.
4 Stadler, Peter F.
3 Bernstein, Aaron
3 Boria, Nicolas
3 Chan, Timothy Moon-Yew
3 Chechik, Shiri
3 Dani, Varsha
3 Franciosa, Paolo Giulio
3 Geiß, Manuela
3 Goldberg, Andrew V.
3 Kaplan, Haim
3 Łącki, Jakub
3 Mostefaoui, Achour
3 Pandurangan, Gopal
3 Pettie, Seth
3 Raynal, Michel
3 Robinson, Peter
3 Scheideler, Christian
3 Sivasubramaniam, Sumathi
3 Whitesides, Sue H.
2 Abam, Mohammad Ali
2 Acar, Umut A.
2 Afshar, Ramtin
2 Alon, Noga
2 Andoni, Alexandr
2 Balzotti, Lorenzo
2 Boyle, Elette
2 Bradford, Phillip G.
2 Brown, Daniel G.
2 Chakraborty, Dibyayan
2 Chan, T.-H. Hubert
2 Chandran, L. Sunil
2 Charalampopoulos, Panagiotis
2 Choudhary, Keerti
2 Cohen, Sarel
2 Ding, Wei
2 Fernández-Baca, David
2 Fich, Faith Ellen
2 Fleischer, Rudolf
2 Gawrychowski, Paweł
2 Ghiyasvand, Mehdi
2 Goel, Aarushi
2 Goodrich, Michael Truman
2 Habib, Michel
2 Haitner, Iftach
2 Henzinger, Thomas A.
2 Hernandez-Rosales, Maribel
2 Hochbaum, Dorit S.
2 Holm, Jacob
2 Iwano, Kazuo
2 Kashyop, Manas Jyoti
2 Katoh, Naoki
2 Khan, Shahbaz
2 Korman, Amos
2 Korman, Matias
2 Kowaluk, Mirosław
2 Kuhn, Fabian
2 Kutyłowski, Mirosław
2 Lenzen, Christoph
2 Lingas, Andrzej
2 Loryś, Krzysztof
2 Loss, Julian
2 Lundell, Eva-Marta
2 Mashreghi, Ali
2 Mathieu, Claire
2 McCormick, S. Thomas
2 Micali, Silvio
2 Molla, Anisur Rahaman
2 Monnot, Jérôme
2 Mossel, Elchanan
2 Nayak, Kartik
2 Orlin, James B.
2 Padinhatteeri, Sajith
2 Pass, Rafael
2 Paz, Ami
2 Pillai, Raji R.
2 Qiu, Ke
2 Queyranne, Maurice
2 Ragde, Prabhakar L.
2 Raghuraman, Srinivasan
...and 431 more Authors
all top 5

Cited in 54 Serials

23 Algorithmica
19 Theoretical Computer Science
17 Distributed Computing
14 SIAM Journal on Computing
10 Discrete Applied Mathematics
7 Journal of Computer and System Sciences
7 Networks
5 Information Processing Letters
5 Information and Computation
5 Random Structures & Algorithms
4 Journal of Mathematical Biology
4 Journal of Cryptology
4 Mathematical Programming. Series A. Series B
3 European Journal of Combinatorics
3 Discrete & Computational Geometry
3 Journal of Parallel and Distributed Computing
3 Computational Geometry
3 Journal of Graph Algorithms and Applications
3 Journal of the ACM
3 Journal of Discrete Algorithms
3 Algorithms
2 Applied Mathematics and Computation
2 Information Sciences
2 Combinatorica
2 Computers & Operations Research
2 SIAM Journal on Discrete Mathematics
2 The Annals of Applied Probability
2 Theory of Computing Systems
2 Journal of Combinatorial Optimization
2 ACM Journal of Experimental Algorithmics
1 Acta Informatica
1 Discrete Mathematics
1 International Journal of Theoretical Physics
1 Journal of Graph Theory
1 Naval Research Logistics
1 Advances in Applied Mathematics
1 Operations Research Letters
1 Applied Mathematical Modelling
1 European Journal of Operational Research
1 SIAM Review
1 SIAM Journal on Optimization
1 Computational Complexity
1 Journal of Functional Programming
1 The Journal of Artificial Intelligence Research (JAIR)
1 Discussiones Mathematicae. Graph Theory
1 Constraints
1 Data Mining and Knowledge Discovery
1 RAIRO. Operations Research
1 Journal of Machine Learning Research (JMLR)
1 Internet Mathematics
1 Parallel Processing Letters
1 Discrete Optimization
1 Transactions on Combinatorics
1 Computer Science Review

Citations by Year

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.