×
Compute Distance To:
Author ID: hromkovic.juraj Recent zbMATH articles by "Hromkovič, Juraj"
Published as: Hromkovič, Juraj; Hromkovic, Juraj; Hromkovič, J.; Hromkovic, J.; Hromkovič, Juray
Homepage: http://www.ite.ethz.ch/people/host/jhromkov/index
External Links: MGP · Wikidata · ResearchGate · dblp · GND · IdRef
Documents Indexed: 186 Publications since 1981, including 17 Books
5 Contributions as Editor
Reviewing Activity: 121 Reviews
Biographic References: 1 Publication
Co-Authors: 103 Co-Authors with 130 Joint Publications
1,759 Co-Co-Authors
all top 5

Co-Authors

61 single-authored
31 Böckenhauer, Hans-Joachim
23 Schnitger, Georg
16 Unger, Walter
15 Klasing, Ralf
13 Seibert, Sebastian
11 Královič, Richard
9 Mömke, Tobias
7 Inoue, Katsushi
7 Královič, Rastislav
7 Proietti, Guido
7 Steffen, Björn
6 Bianchi, Maria Paola
6 Ďuriš, Pavol
6 Komm, Dennis
6 Krug, Sacha
6 Monien, Burkhard
6 Sprock, Andreas
6 Widmayer, Peter
5 Karhumaki, Juhani
5 Takanami, Itsuo
5 Wagener, Hubert
4 Bongartz, Dirk
4 Freiermuth, Karin
4 Keller, Lucia
4 Pardubská, Dana
4 Rossmanith, Peter
4 Rovan, Branislav
4 Sauerhoff, Martin
4 Slobodová, Anna
3 Forlizzi, Luca
3 Hosoda, Jun
3 Izumi, Taisuke
3 Jeschke, Claus-Dieter
3 Kari, Jarkko
3 Kari, Lila
3 Kneis, Joachim
3 Kupke, Joachim
3 Ono, Hirotaka
3 Smula, Jasmin
3 Steinhöfel, Kathleen K.
3 Steinová, Monika
3 Sýkora, Ondrej
3 Wada, Koichi
2 Barhum, Kfir
2 Barot, Michael
2 Burjons, Elisabet
2 Dassow, Jürgen
2 Frei, Fabian
2 Klauck, Hartmut
2 Kováč, Ivan
2 Muñoz, Xavier
2 Štefanec, Richard
2 Waczulík, Juraj
2 Yukna, Stasys P.
1 Bilò, Davide
1 Černá, Ivana
1 Chrobak, Marek
1 Clemente, Jhoirene
1 Dietzfelbinger, Martin
1 Dobrev, Stefan
1 Feldmann, Rainer
1 Forišek, Michal
1 Ftáčnik, Milan
1 Gebauer, Heidi
1 Gubáš, Xaver
1 Gyimóthy, Tibor
1 Ito, Akira
1 Janiga, Ladislav
1 Jefferey, Keith
1 Kanarek, Przemysawa
1 Kelemen, Jozef
1 Koubek, Vaclav
1 Krause, Matthias
1 Kudahl, Christian
1 Kupková, Erika
1 Lory, Krzysztof
1 Loryś, Krzysztof
1 Lozhkin, Sergei A.
1 Madhavapeddy, Seshu
1 Meinel, Christoph
1 Mertan, Jozef
1 Müller, Vladimír
1 Mysliwietz, Peter
1 Nagl, Manfred
1 Nunkesser, Marc
1 Peine, Regine
1 Pelc, Andrzej
1 Petersen, Holger
1 Procházka, Juraj
1 Ruzicka, Peter
1 Rybko, Andrej I.
1 Sapozhenko, Aleksandr Antonovich
1 Škalikova, Nadežda A.
1 Stöhr, Elena A.
1 Šuster, B.
1 Vrto, Imrich
1 Vukolić, Marko
1 Waack, Stephan
1 Wagner, Klaus W.
1 Westfechtel, Bernhard
...and 3 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

130 Publications have been cited 809 times in 463 Documents Cited by Year
Dissemination of information in interconnection networks (broadcasting & gossiping). Zbl 0840.68088
Hromkovič, Juraj; Klasing, Ralf; Monien, Burkhard; Peine, Regine
59
1996
Communication complexity and parallel computing. Zbl 0873.68098
Hromkovič, Juraj
38
1997
Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance. Zbl 1067.68016
Hromkovič, Juraj; Klasing, Ralf; Pelc, Andrzej; Ružička, Peter; Unger, Walter
36
2005
Information complexity of online problems. Zbl 1287.68083
Hromkovič, Juraj; Královič, Rastislav; Královič, Richard
29
2010
Communication complexity method for measuring nondeterminism in finite automata. Zbl 1009.68067
Hromkovič, Juraj; Seibert, Sebastian; Karhumäki, Juhani; Klauck, Hartmut; Schnitger, Georg
29
2002
Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata. Zbl 1014.68093
Hromkovič, Juraj; Seibert, Sebastian; Wilke, Thomas
25
2001
On the hardness of reoptimization. Zbl 1133.68351
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Mömke, Tobias; Widmayer, Peter
20
2008
On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Zbl 1007.68065
Hromkovič, Juraj; Schnitger, Georg
18
2001
On the approximability of TSP on local modifications of optimally solved instances. Zbl 1206.90134
Böckenhauer, Hans-Joachim; Forlizzi, Luca; Hromkovič, Juraj; Kneis, Joachim; Kupke, Joachim; Proietti, Guido; Widmayer, Peter
16
2007
The string guessing problem as a method to prove lower bounds on the advice complexity. Zbl 1360.68908
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Komm, Dennis; Krug, Sacha; Smula, Jasmin; Sprock, Andreas
15
2014
Approximation algorithms for the TSP with sharpened triangle inequality. Zbl 1338.68289
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Klasing, Ralf; Seibert, Sebastian; Unger, Walter
15
2000
Reoptimization of Steiner trees. Zbl 1155.68574
Bilò, Davide; Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Královič, Richard; Mömke, Tobias; Widmayer, Peter; Zych, Anna
15
2008
On the power of synchronization in parallel computations. Zbl 0734.68036
Hromkovič, Juraj; Karhumäki, Juhani; Rovan, Branislav; Slobodová, Anna
15
1991
One way multihead deterministic finite automata. Zbl 0504.68049
Hromkovic, J.
14
1983
An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality (extended abstract). Zbl 1028.90044
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Klasing, Ralf; Seibert, Sebastian; Unger, Walter
14
2000
A comparison of two lower-bound methods for communication complexity. Zbl 0874.68150
Dietzfelbinger, Martin; Hromkovič, Juraj; Schnitger, Georg
14
1996
On the power of advice and randomization for the disjoint path allocation problem. Zbl 1432.68009
Barhum, Kfir; Böckenhauer, Hans-Joachim; Forišek, Michal; Gebauer, Heidi; Hromkovič, Juraj; Krug, Sacha; Smula, Jasmin; Steffen, Björn
12
2014
Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser’s separation. Zbl 1039.68068
Hromkovič, Juraj; Schnitger, Georg
12
2003
On the power of alternation in automata theory. Zbl 0582.68018
Hromkovič, Juraj
12
1985
Descriptional complexity of finite automata: concepts and open problems. Zbl 1094.68576
Hromkovič, Juraj
12
2002
Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Zbl 1094.90036
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Klasing, Ralf; Seibert, Sebastian; Unger, Walter
12
2002
Reoptimization of Steiner trees: changing the terminal set. Zbl 1192.68471
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Královič, Richard; Mömke, Tobias; Rossmanith, Peter
11
2009
Online coloring of bipartite graphs with and without advice. Zbl 1314.68403
Bianchi, Maria Paola; Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Keller, Lucia
11
2012
Online coloring of bipartite graphs with and without advice. Zbl 1314.68404
Bianchi, Maria Paola; Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Keller, Lucia
10
2014
Optimal algorithms for dissemination of information in generalized communication modes. Zbl 0823.68041
Feldmann, R.; Hromkovič, Juraj; Madhavapeddy, S.; Monien, B.; Mysliwietz, P.
10
1994
Gossiping in vertex-disjoint paths mode in \(d\)-dimensional grids and planar graphs. Zbl 1096.68514
Hromkovič, Juraj; Klasing, Ralf; Stöhr, Elena A.; Wagener, Hubert
9
1995
Deterministic versus nondeterministic space in terms of synchronized alternating machines. Zbl 0821.68056
Hromkovič, Juraj; Rovan, Branislav; Slobodova, Anna
9
1994
On the power of synchronization in parallel computations. Zbl 0755.68045
Dassow, Jürgen; Hromkovič, Juraj; Karhumäki, Juhani; Rovan, Branislav; Slobodová, Anna
8
1989
The parameterized approximability of TSP with deadlines. Zbl 1148.68052
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Kneis, Joachim; Kupke, Joachim
8
2007
Tradeoffs between nondeterminism and complexity for communication protocols and branching programs (extended abstract). Zbl 0959.68522
Hromkovič, Juraj; Sauerhoff, Martin
8
2000
Algorithmics for hard problems. 2nd ed., corr. 2nd printing. Zbl 1069.68642
Hromkovič, Juraj
8
2004
The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract). Zbl 1382.68333
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Komm, Dennis; Krug, Sacha; Smula, Jasmin; Sprock, Andreas
8
2013
Tradeoffs for language recognition on alternating machines. Zbl 0667.68060
Hromkovič, Juraj
7
1989
The power of nondeterminism and randomness for oblivious branching programs. Zbl 1039.68083
Hromkovič, Juraj; Sauerhoff, Martin
7
2003
Design and analysis of randomized algorithms. Introduction to design paradigms. Zbl 1083.68146
Hromkovič, Juraj
7
2005
On the power of one-way synchronized alternating machines with small space. Zbl 0769.68030
Hromkovič, Juraj; Inoue, Katsushi; Rovan, Branislav; Slobodová, Anna; Takanami, Itsuo; Wagner, Klaus W.
6
1992
Job shop scheduling with unit length tasks: bounds and algorithms. Zbl 1186.90051
Hromkovič, Juraj; Mömke, Tobias; Steinhöfel, Kathleen; Widmayer, Peter
6
2007
On the power of Las Vegas II: Two-way finite automata. Zbl 0983.68098
Hromkovič, J.; Schnitger, G.
6
2001
Hierarchy of reversal and zerotesting bounded multicounter machines. Zbl 0582.68049
Hromkovič, J.
6
1984
On multi-partition communication complexity. Zbl 1073.68030
Ďuriš, Pavol; Hromkovič, Juraj; Jukna, Stasys; Sauerhoff, Martin; Schnitger, Georg
6
2004
Measures of nondeterminism in finite automata. Zbl 0973.68114
Hromkovič, Juray; Karhumäki, Juhani; Klauck, Hartmut; Schnitger, Georg; Seibert, Sebastian
6
2000
One-way simple multihead finite automata are not closed under concatenation. Zbl 0523.68070
Duris, Pavol; Hromkovic, Juraj
5
1983
Fooling a two-way nondeterministic multihead automaton with reversal number restriction. Zbl 0565.68078
Hromkovič, Juraj
5
1985
Some complexity aspects of VLSI computations. I: A framework for the study of information transfer in VLSI circuits. Zbl 0644.94027
Hromkovič, Juraj
5
1988
Comparing the size of NFAs with and without \(\epsilon\)-transitions. Zbl 1115.68098
Hromkovič, Juraj; Schnitger, Georg
5
2007
Alternating multicounter machines with constant number of reversals. Zbl 0579.68033
Hromkovič, Juraj
5
1985
Stability of approximation algorithms and the knapsack problem. Zbl 0945.68074
Hromkovič, Juraj
5
1999
Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Zbl 0961.68058
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Klasing, Ralf; Seibert, Sebastian; Unger, Walter
5
2000
Communication protocols – an exemplary study of the power of randomness. Zbl 1056.68087
Hromkovič, Juraj
5
2001
Optimal algorithms for broadcast and gossip in the edge-disjoint modes. Zbl 0878.68070
Hromkovič, Juraj; Klasing, Ralf; Unger, Walter; Wagener, Hubert
5
1997
On the approximability and hardness of minimum topic connected overlay and its special instances. Zbl 1238.68063
Hosoda, Jun; Hromkovič, Juraj; Izumi, Taisuke; Ono, Hirotaka; Steinová, Monika; Wada, Koichi
5
2012
On the power of randomness versus advice in online computation. Zbl 1367.68340
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Komm, Dennis; Královič, Richard; Rossmanith, Peter
5
2012
Relation between Chomsky hierarchy and communication complexity hierarchy. Zbl 0631.68068
Hromkovič, Juraj
4
1986
Nondeterministic communication with a limited number of advice bits. Zbl 1040.68046
Hromkovic, Juraj; Schnitger, Georg
4
2003
On the approximation hardness of some generalizations of TSP. (Extended abstract). Zbl 1141.90507
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Kneis, Joachim; Kupke, Joachim
4
2006
Reversal bounded multicounter machines. Zbl 0579.68032
Hromkovič, Juraj
4
1985
The Steiner tree reoptimization problem with sharpened triangle inequality (extended abstract). Zbl 1284.68654
Böckenhauer, Hans-Joachim; Freiermuth, Karin; Hromkovič, Juraj; Mömke, Tobias; Sprock, Andreas; Steffen, Björn
4
2010
On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality. Zbl 1093.68070
Böckenhauer, Hans-Joachim; Bongartz, Dirk; Hromkovič, Juraj; Klasing, Ralf; Proietti, Guido; Seibert, Sebastian; Unger, Walter
4
2004
Optimal algorithms for dissemination of information in some interconnection networks. Zbl 0773.68007
Hromkovič, Juraj; Jeschke, Claus-Dieter; Monien, Burkhard
4
1993
Lower bounds for language recognition on two-dimensional alternating multihead machines. Zbl 0678.68037
Hromkovič, Juraj; Inoue, Katsushi; Takanami, Itsuo
4
1989
On \(k\)-edge-connectivity problems with sharpened triangle inequality. Zbl 1032.68116
Böckenhauer, Hans-Joachim; Bongartz, Dirk; Hromkovič, Juraj; Klasing, Ralf; Proietti, Guido; Seibert, Sebastian; Unger, Walter
4
2003
On the power of Las Vegas. II: Two-way finite automata. Zbl 0939.68071
Hromkovič, Juraj; Schnitger, Georg
4
1999
Knowing all optimal solutions does not help for TSP reoptimization. Zbl 1331.90060
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Sprock, Andreas
4
2011
On probabilistic pushdown automata. Zbl 1205.68202
Hromkovič, Juraj; Schnitger, Georg
4
2010
On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles. Zbl 1381.68095
Bianchi, Maria Paola; Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Krug, Sacha; Steffen, Björn
4
2013
On one-way two-head deterministic finite state automata. Zbl 0605.68079
Hromkovič, Juraj
3
1985
On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles. Zbl 1382.68099
Bianchi, Maria Paola; Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Krug, Sacha; Steffen, Björn
3
2014
On the hardness of reoptimization with multiple given solutions. Zbl 1254.90185
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Sprock, Andreas
3
2011
Steiner tree reoptimization in graphs with sharpened triangle inequality. Zbl 1238.68105
Böckenhauer, Hans-Joachim; Freiermuth, Karin; Hromkovič, Juraj; Mömke, Tobias; Sprock, Andreas; Steffen, Björn
3
2012
Nondeterministic communication with a limited number of advice bits. Zbl 0922.68060
Hromkovic, J.; Schnitger, G.
3
1996
On embeddings in cycles. Zbl 0826.68012
Hromkovič, Juraj; Müller, Vladimír; Sýkora, Ondrej; Vrťo, Imrich
3
1995
On the stability of approximation for Hamiltonian path problems. Zbl 1148.05040
Forlizzi, Luca; Hromkovič, Juraj; Proietti, Guido; Seibert, Sebastian
3
2006
On \(k\)-connectivity problems with sharpened triangle inequality. Zbl 1154.90576
Böckenhauer, Hans-Joachim; Bongartz, Dirk; Hromkovič, Juraj; Klasing, Ralf; Proietti, Guido; Seibert, Sebastian; Unger, Walter
3
2008
Stability of approximation algorithms for hard optimization problems. Zbl 0961.65060
Hromkovič, Juraj
3
1999
Algorithmics for hard problems. Introduction to combinatorial optimization, randomization, approximation, and heuristics. Zbl 0968.68190
Hromkovič, Juraj
3
2000
The complexity of systolic dissemination of information in interconnection networks. Zbl 0888.68014
Hromkovič, J.; Klasing, R.; Unger, W.; Wagener, H.; Pardubská, D.
3
1994
On the hardness of determining small NFA’s and of proving lower bounds on their sizes. Zbl 1159.68017
Hromkovič, Juraj; Schnitger, Georg
3
2008
Advice complexity of the online search problem. Zbl 1478.68452
Clemente, Jhoirene; Hromkovič, Juraj; Komm, Dennis; Kudahl, Christian
3
2016
Ambiguity and communication. Zbl 1246.68146
Hromkovič, Juraj; Schnitger, Georg
3
2011
Hierarchy of reversal bounded one-way multicounter machines. Zbl 0607.68034
Hromkovič, Juraj
2
1986
Online graph coloring with advice and randomized adversary (extended abstract). Zbl 1442.68271
Burjons, Elisabet; Hromkovič, Juraj; Muñoz, Xavier; Unger, Walter
2
2016
Nonlinear lower bounds on the number of processors of circuits with sublinear separators. Zbl 0747.94025
Hromkovič, Juraj
2
1991
A note on realtime one-way synchronized alternating one-counter automata. Zbl 0776.68039
Hromkovič, Juraj; Inoue, Katsushi
2
1993
The bisection problem for graphs of degree 4. (Configuring transputer systems). Zbl 0768.68145
Hromkovič, Juraj; Monien, Burkhard
2
1991
Pushdown automata and multicounter machines, a comparison of computation modes. Zbl 1039.68554
Hromkovič, Juraj; Schnitger, Georg
2
2003
Communication complexity and sequential computation. Zbl 0941.68090
Hromkovič, Juraj; Schnitger, Georg
2
1997
Nonlinear lower bound for real-time branching programs. Zbl 0579.68031
Ftáčnik, Milan; Hromkovič, Juraj
2
1985
On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA’s. Zbl 1173.68035
Hromkovič, Juraj; Petersen, Holger; Schnitger, Georg
2
2009
On the power of randomized pushdown automata. Zbl 1073.68047
Hromkovič, Juraj; Schnitger, Georg
2
2002
On the power of randomized multicounter machines. Zbl 1078.68037
Hromkovič, Juraj; Schnitger, Georg
2
2005
Note on optimal gossiping in some weak-connected graphs. Zbl 0824.68010
Hromkovič, Juraj; Jeschke, Claus-Dieter; Monien, Burkhard
2
1994
The advantages of a new approach to defining the communication complexity for VLSI. Zbl 0651.68050
Hromkovič, Juraj
2
1988
Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits. Zbl 0674.68033
Hromkovič, Juraj; Krause, Matthias; Meinel, Christoph; Waack, Stephan
2
1990
Some complexity aspects of VLSI computations. VI: Communication complexity. Zbl 0676.68014
Hromkovič, Juraj
2
1989
NFAs with and without \(\epsilon\)-transitions. Zbl 1082.68052
Hromkovič, Juraj; Schnitger, Georg
2
2005
Theoretical computer science. Introduction to automata, computability, complexity, algorithmics, randomization, communication, and cryptography. Zbl 1113.68001
Hromkovič, Juraj
2
2004
Graph-theoretic concepts in computer science. 30th international workshop, WG 2004, Bad Honnef, Germany, June 21–23, 2004. Revised papers. Zbl 1067.68006
2
2004
Online graph coloring against a randomized adversary. Zbl 1397.68229
Burjons, Elisabet; Hromkovič, Juraj; Královič, Rastislav; Královič, Richard; Muñoz, Xavier; Unger, Walter
2
2018
On the sizes of permutation networks and consequences for efficient simulation of hypercube algorithms on bounded-degree networks. Zbl 1379.68013
Hromkovič, J.; Loryś, K.; Kanarek, P.; Klasing, R.; Unger, W.; Wagener, H.
2
1995
Zerotesting bounded one-way multicounter machines. Zbl 0619.68048
Ďuriš, Pavol; Hromkovič, Juraj
1
1987
Online graph coloring against a randomized adversary. Zbl 1397.68229
Burjons, Elisabet; Hromkovič, Juraj; Královič, Rastislav; Královič, Richard; Muñoz, Xavier; Unger, Walter
2
2018
Advice complexity of the online search problem. Zbl 1478.68452
Clemente, Jhoirene; Hromkovič, Juraj; Komm, Dennis; Kudahl, Christian
3
2016
Online graph coloring with advice and randomized adversary (extended abstract). Zbl 1442.68271
Burjons, Elisabet; Hromkovič, Juraj; Muñoz, Xavier; Unger, Walter
2
2016
The complexity of paging against a probabilistic adversary. Zbl 1442.68276
Dobrev, Stefan; Hromkovič, Juraj; Komm, Dennis; Královič, Richard; Královič, Rastislav; Mömke, Tobias
1
2016
The string guessing problem as a method to prove lower bounds on the advice complexity. Zbl 1360.68908
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Komm, Dennis; Krug, Sacha; Smula, Jasmin; Sprock, Andreas
15
2014
On the power of advice and randomization for the disjoint path allocation problem. Zbl 1432.68009
Barhum, Kfir; Böckenhauer, Hans-Joachim; Forišek, Michal; Gebauer, Heidi; Hromkovič, Juraj; Krug, Sacha; Smula, Jasmin; Steffen, Björn
12
2014
Online coloring of bipartite graphs with and without advice. Zbl 1314.68404
Bianchi, Maria Paola; Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Keller, Lucia
10
2014
On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles. Zbl 1382.68099
Bianchi, Maria Paola; Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Krug, Sacha; Steffen, Björn
3
2014
A technique to obtain hardness results for randomized online algorithms – a survey. Zbl 1323.68575
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Komm, Dennis
1
2014
The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract). Zbl 1382.68333
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Komm, Dennis; Krug, Sacha; Smula, Jasmin; Sprock, Andreas
8
2013
On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles. Zbl 1381.68095
Bianchi, Maria Paola; Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Krug, Sacha; Steffen, Björn
4
2013
Determinism vs. nondeterminism for two-way automata: representing the meaning of states by logical formulæ. Zbl 1293.68188
Hromkovič, Juraj; Královič, Rastislav; Královič, Richard; Štefanec, Richard
1
2013
Online coloring of bipartite graphs with and without advice. Zbl 1314.68403
Bianchi, Maria Paola; Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Keller, Lucia
11
2012
On the approximability and hardness of minimum topic connected overlay and its special instances. Zbl 1238.68063
Hosoda, Jun; Hromkovič, Juraj; Izumi, Taisuke; Ono, Hirotaka; Steinová, Monika; Wada, Koichi
5
2012
On the power of randomness versus advice in online computation. Zbl 1367.68340
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Komm, Dennis; Královič, Richard; Rossmanith, Peter
5
2012
Steiner tree reoptimization in graphs with sharpened triangle inequality. Zbl 1238.68105
Böckenhauer, Hans-Joachim; Freiermuth, Karin; Hromkovič, Juraj; Mömke, Tobias; Sprock, Andreas; Steffen, Björn
3
2012
Knowing all optimal solutions does not help for TSP reoptimization. Zbl 1331.90060
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Sprock, Andreas
4
2011
On the hardness of reoptimization with multiple given solutions. Zbl 1254.90185
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Sprock, Andreas
3
2011
Ambiguity and communication. Zbl 1246.68146
Hromkovič, Juraj; Schnitger, Georg
3
2011
Information complexity of online problems. Zbl 1287.68083
Hromkovič, Juraj; Královič, Rastislav; Královič, Richard
29
2010
The Steiner tree reoptimization problem with sharpened triangle inequality (extended abstract). Zbl 1284.68654
Böckenhauer, Hans-Joachim; Freiermuth, Karin; Hromkovič, Juraj; Mömke, Tobias; Sprock, Andreas; Steffen, Björn
4
2010
On probabilistic pushdown automata. Zbl 1205.68202
Hromkovič, Juraj; Schnitger, Georg
4
2010
Reoptimization of Steiner trees: changing the terminal set. Zbl 1192.68471
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Královič, Richard; Mömke, Tobias; Rossmanith, Peter
11
2009
On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA’s. Zbl 1173.68035
Hromkovič, Juraj; Petersen, Holger; Schnitger, Georg
2
2009
Ambiguity and communication. Zbl 1236.68169
Hromkovič, Juraj; Schnitger, Georg
1
2009
Lower bounds on the size of sweeping automata. Zbl 1192.68413
Hromkovič, Juraj; Schnitger, Georg
1
2009
On the hardness of reoptimization. Zbl 1133.68351
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Mömke, Tobias; Widmayer, Peter
20
2008
Reoptimization of Steiner trees. Zbl 1155.68574
Bilò, Davide; Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Královič, Richard; Mömke, Tobias; Widmayer, Peter; Zych, Anna
15
2008
On \(k\)-connectivity problems with sharpened triangle inequality. Zbl 1154.90576
Böckenhauer, Hans-Joachim; Bongartz, Dirk; Hromkovič, Juraj; Klasing, Ralf; Proietti, Guido; Seibert, Sebastian; Unger, Walter
3
2008
On the hardness of determining small NFA’s and of proving lower bounds on their sizes. Zbl 1159.68017
Hromkovič, Juraj; Schnitger, Georg
3
2008
On the approximability of TSP on local modifications of optimally solved instances. Zbl 1206.90134
Böckenhauer, Hans-Joachim; Forlizzi, Luca; Hromkovič, Juraj; Kneis, Joachim; Kupke, Joachim; Proietti, Guido; Widmayer, Peter
16
2007
The parameterized approximability of TSP with deadlines. Zbl 1148.68052
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Kneis, Joachim; Kupke, Joachim
8
2007
Job shop scheduling with unit length tasks: bounds and algorithms. Zbl 1186.90051
Hromkovič, Juraj; Mömke, Tobias; Steinhöfel, Kathleen; Widmayer, Peter
6
2007
Comparing the size of NFAs with and without \(\epsilon\)-transitions. Zbl 1115.68098
Hromkovič, Juraj; Schnitger, Georg
5
2007
Stability of approximation algorithms or parameterization of the approximation ratio. Zbl 1147.90417
Böckenhauer, Hans-Joachim; Hromkovič, Juraj
1
2007
On the approximation hardness of some generalizations of TSP. (Extended abstract). Zbl 1141.90507
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Kneis, Joachim; Kupke, Joachim
4
2006
On the stability of approximation for Hamiltonian path problems. Zbl 1148.05040
Forlizzi, Luca; Hromkovič, Juraj; Proietti, Guido; Seibert, Sebastian
3
2006
Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance. Zbl 1067.68016
Hromkovič, Juraj; Klasing, Ralf; Pelc, Andrzej; Ružička, Peter; Unger, Walter
36
2005
Design and analysis of randomized algorithms. Introduction to design paradigms. Zbl 1083.68146
Hromkovič, Juraj
7
2005
On the power of randomized multicounter machines. Zbl 1078.68037
Hromkovič, Juraj; Schnitger, Georg
2
2005
NFAs with and without \(\epsilon\)-transitions. Zbl 1082.68052
Hromkovič, Juraj; Schnitger, Georg
2
2005
Algorithmics for hard problems. 2nd ed., corr. 2nd printing. Zbl 1069.68642
Hromkovič, Juraj
8
2004
On multi-partition communication complexity. Zbl 1073.68030
Ďuriš, Pavol; Hromkovič, Juraj; Jukna, Stasys; Sauerhoff, Martin; Schnitger, Georg
6
2004
On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality. Zbl 1093.68070
Böckenhauer, Hans-Joachim; Bongartz, Dirk; Hromkovič, Juraj; Klasing, Ralf; Proietti, Guido; Seibert, Sebastian; Unger, Walter
4
2004
Theoretical computer science. Introduction to automata, computability, complexity, algorithmics, randomization, communication, and cryptography. Zbl 1113.68001
Hromkovič, Juraj
2
2004
Graph-theoretic concepts in computer science. 30th international workshop, WG 2004, Bad Honnef, Germany, June 21–23, 2004. Revised papers. Zbl 1067.68006
2
2004
On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata. Zbl 1069.68061
Ďuriš, Pavol; Hromkovič, Juraj; Inoue, Katsushi
1
2004
Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser’s separation. Zbl 1039.68068
Hromkovič, Juraj; Schnitger, Georg
12
2003
The power of nondeterminism and randomness for oblivious branching programs. Zbl 1039.68083
Hromkovič, Juraj; Sauerhoff, Martin
7
2003
Nondeterministic communication with a limited number of advice bits. Zbl 1040.68046
Hromkovic, Juraj; Schnitger, Georg
4
2003
On \(k\)-edge-connectivity problems with sharpened triangle inequality. Zbl 1032.68116
Böckenhauer, Hans-Joachim; Bongartz, Dirk; Hromkovič, Juraj; Klasing, Ralf; Proietti, Guido; Seibert, Sebastian; Unger, Walter
4
2003
Pushdown automata and multicounter machines, a comparison of computation modes. Zbl 1039.68554
Hromkovič, Juraj; Schnitger, Georg
2
2003
Communication complexity method for measuring nondeterminism in finite automata. Zbl 1009.68067
Hromkovič, Juraj; Seibert, Sebastian; Karhumäki, Juhani; Klauck, Hartmut; Schnitger, Georg
29
2002
Descriptional complexity of finite automata: concepts and open problems. Zbl 1094.68576
Hromkovič, Juraj
12
2002
Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Zbl 1094.90036
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Klasing, Ralf; Seibert, Sebastian; Unger, Walter
12
2002
On the power of randomized pushdown automata. Zbl 1073.68047
Hromkovič, Juraj; Schnitger, Georg
2
2002
On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality. Zbl 1027.68097
Böckenhauer, Hans-Joachim; Bongartz, Dirk; Hromkovič, Juraj; Klasing, Ralf; Proietti, Guido; Seibert, Sebastian; Unger, Walter
1
2002
Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata. Zbl 1014.68093
Hromkovič, Juraj; Seibert, Sebastian; Wilke, Thomas
25
2001
On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Zbl 1007.68065
Hromkovič, Juraj; Schnitger, Georg
18
2001
On the power of Las Vegas II: Two-way finite automata. Zbl 0983.68098
Hromkovič, J.; Schnitger, G.
6
2001
Communication protocols – an exemplary study of the power of randomness. Zbl 1056.68087
Hromkovič, Juraj
5
2001
Job shop scheduling with unit length tasks: bounds and algorithms. Zbl 1042.90020
Hromkovic, Juraj; Steinhöfel, Kathleen; Widmayer, Peter
1
2001
Randomized communication protocols (a survey). Zbl 1054.68060
Hromkovič, Juraj
1
2001
On multipartition communication complexity (extended abstract). Zbl 0976.68514
Duriš, Pavol; Hromkovič, Juraj; Jukna, Stasys; Sauerhoff, Martin; Schnitger, Georg
1
2001
Approximation algorithms for the TSP with sharpened triangle inequality. Zbl 1338.68289
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Klasing, Ralf; Seibert, Sebastian; Unger, Walter
15
2000
An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality (extended abstract). Zbl 1028.90044
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Klasing, Ralf; Seibert, Sebastian; Unger, Walter
14
2000
Tradeoffs between nondeterminism and complexity for communication protocols and branching programs (extended abstract). Zbl 0959.68522
Hromkovič, Juraj; Sauerhoff, Martin
8
2000
Measures of nondeterminism in finite automata. Zbl 0973.68114
Hromkovič, Juray; Karhumäki, Juhani; Klauck, Hartmut; Schnitger, Georg; Seibert, Sebastian
6
2000
Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Zbl 0961.68058
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Klasing, Ralf; Seibert, Sebastian; Unger, Walter
5
2000
Algorithmics for hard problems. Introduction to combinatorial optimization, randomization, approximation, and heuristics. Zbl 0968.68190
Hromkovič, Juraj
3
2000
Stability of approximation algorithms and the knapsack problem. Zbl 0945.68074
Hromkovič, Juraj
5
1999
On the power of Las Vegas. II: Two-way finite automata. Zbl 0939.68071
Hromkovič, Juraj; Schnitger, Georg
4
1999
Stability of approximation algorithms for hard optimization problems. Zbl 0961.65060
Hromkovič, Juraj
3
1999
Communication complexity and lower bounds on multilective computations. Zbl 0946.68052
Hromkovič, Juraj
1
1999
Communication complexity and parallel computing. Zbl 0873.68098
Hromkovič, Juraj
38
1997
Optimal algorithms for broadcast and gossip in the edge-disjoint modes. Zbl 0878.68070
Hromkovič, Juraj; Klasing, Ralf; Unger, Walter; Wagener, Hubert
5
1997
Communication complexity and sequential computation. Zbl 0941.68090
Hromkovič, Juraj; Schnitger, Georg
2
1997
Dissemination of information in interconnection networks (broadcasting & gossiping). Zbl 0840.68088
Hromkovič, Juraj; Klasing, Ralf; Monien, Burkhard; Peine, Regine
59
1996
A comparison of two lower-bound methods for communication complexity. Zbl 0874.68150
Dietzfelbinger, Martin; Hromkovič, Juraj; Schnitger, Georg
14
1996
Nondeterministic communication with a limited number of advice bits. Zbl 0922.68060
Hromkovic, J.; Schnitger, G.
3
1996
Two lower bounds on distributive generation of languages. Zbl 0843.68052
Hromkovič, Juraj; Kari, Jarkko; Kari, Lila; Pardubská, Dana
1
1996
Gossiping in vertex-disjoint paths mode in \(d\)-dimensional grids and planar graphs. Zbl 1096.68514
Hromkovič, Juraj; Klasing, Ralf; Stöhr, Elena A.; Wagener, Hubert
9
1995
On embeddings in cycles. Zbl 0826.68012
Hromkovič, Juraj; Müller, Vladimír; Sýkora, Ondrej; Vrťo, Imrich
3
1995
On the sizes of permutation networks and consequences for efficient simulation of hypercube algorithms on bounded-degree networks. Zbl 1379.68013
Hromkovič, J.; Loryś, K.; Kanarek, P.; Klasing, R.; Unger, W.; Wagener, H.
2
1995
Optimal algorithms for dissemination of information in generalized communication modes. Zbl 0823.68041
Feldmann, R.; Hromkovič, Juraj; Madhavapeddy, S.; Monien, B.; Mysliwietz, P.
10
1994
Deterministic versus nondeterministic space in terms of synchronized alternating machines. Zbl 0821.68056
Hromkovič, Juraj; Rovan, Branislav; Slobodova, Anna
9
1994
The complexity of systolic dissemination of information in interconnection networks. Zbl 0888.68014
Hromkovič, J.; Klasing, R.; Unger, W.; Wagener, H.; Pardubská, D.
3
1994
Note on optimal gossiping in some weak-connected graphs. Zbl 0824.68010
Hromkovič, Juraj; Jeschke, Claus-Dieter; Monien, Burkhard
2
1994
Some hierarchies for the communication complexity measures of cooperating grammar systems. Zbl 0805.68043
Hromkovič, Juraj; Kari, Jarkko; Kari, Lila
1
1994
Optimal algorithms for dissemination of information in some interconnection networks. Zbl 0773.68007
Hromkovič, Juraj; Jeschke, Claus-Dieter; Monien, Burkhard
4
1993
A note on realtime one-way synchronized alternating one-counter automata. Zbl 0776.68039
Hromkovič, Juraj; Inoue, Katsushi
2
1993
On the power of one-way synchronized alternating machines with small space. Zbl 0769.68030
Hromkovič, Juraj; Inoue, Katsushi; Rovan, Branislav; Slobodová, Anna; Takanami, Itsuo; Wagner, Klaus W.
6
1992
Lower bounds on the area complexity of Boolean circuits. Zbl 0769.68045
Hromkovič, Juraj; Ložkin, Sergej A.; Rybko, Andrej I.; Sapoženko, Alexander A.; Škalikova, Nadežda A.
1
1992
On synchronized Lindenmayer picture languages. Zbl 0771.68073
Dassow, Jürgen; Hromkovič, Juraj
1
1992
On the power of synchronization in parallel computations. Zbl 0734.68036
Hromkovič, Juraj; Karhumäki, Juhani; Rovan, Branislav; Slobodová, Anna
15
1991
Nonlinear lower bounds on the number of processors of circuits with sublinear separators. Zbl 0747.94025
Hromkovič, Juraj
2
1991
The bisection problem for graphs of degree 4. (Configuring transputer systems). Zbl 0768.68145
Hromkovič, Juraj; Monien, Burkhard
2
1991
On the power of two-dimensional synchronized alternating finite automata. Zbl 0737.68060
Hromkovič, Juraj; Inoue, Katsushi; Ito, Akira; Takanami, Itsuo
1
1991
On problems for which no oracle can help. Zbl 0674.68031
Hromkovič, Juraj
1
1991
Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits. Zbl 0674.68033
Hromkovič, Juraj; Krause, Matthias; Meinel, Christoph; Waack, Stephan
2
1990
...and 30 more Documents
all top 5

Cited by 556 Authors

55 Hromkovič, Juraj
29 Böckenhauer, Hans-Joachim
21 Salomaa, Kai T.
19 Komm, Dennis
18 Královič, Richard
14 Mömke, Tobias
12 Jirásková, Galina
11 Klasing, Ralf
10 Geffert, Viliam
10 Harutyunyan, Hovhannes A.
10 Kutrib, Martin
9 Holzer, Markus
9 Královič, Rastislav
9 Schnitger, Georg
9 Seibert, Sebastian
8 Ibarra, Oscar H.
8 Unger, Walter
8 Yu, Sheng
7 Bollig, Beate
7 Boyar, Joan F.
7 Gargano, Luisa
7 Inoue, Katsushi
7 Kamali, Shahin
7 Paschos, Vangelis Th.
7 Pérennes, Stéphane
7 Pighizzini, Giovanni
6 Bilò, Davide
6 Favrholdt, Lene Monrad
6 Fraigniaud, Pierre
6 Krug, Sacha
6 Larsen, Kim Skak
6 Liestman, Arthur L.
6 Theis, Dirk Oliver
5 Boria, Nicolas
5 Gruber, Hermann
5 Jiang, Tao
5 Kapoutsis, Christos A.
5 Malcher, Andreas
5 Monnot, Jérôme
5 Rescigno, Adele Anna
5 Slobodová, Anna
5 Takanami, Itsuo
5 Vaccaro, Ugo
4 Bermond, Jean-Claude
4 Bianchi, Maria Paola
4 Chen, Li-Hsuan
4 Czyzowicz, Jurek
4 Ďuriš, Pavol
4 Fertin, Guillaume
4 Gregor, Petr
4 Hung, Ling-Ju
4 Kowalski, Dariusz R.
4 Kudahl, Christian
4 López-Ortiz, Alejandro
4 Manthey, Bodo
4 Niedermeier, Rolf
4 Peters, Joseph G.
4 Proietti, Guido
4 Rossmanith, Peter
4 Sauerhoff, Martin
4 Škrekovski, Riste
4 Trân, Nicholas Q.
4 Vukašinović, Vida
4 Yakaryılmaz, Abuzer
4 Zych, Anna
3 Anselmo, Marcella
3 Dar, Muhammad Abid
3 De Marco, Gianluca
3 Dobrev, Stefan
3 Farley, Arthur M.
3 Fischer, Andreas M.
3 Hsieh, Sun-Yuan
3 Itsykson, Dmitry M.
3 Karhumaki, Juhani
3 Kranakis, Evangelos Konstantinou
3 Krause, Matthias
3 Madonia, Maria
3 Martinovic, John
3 Mereghetti, Carlo
3 Mignot, Ludovic
3 Mikkelsen, Jesper W.
3 Okhotin, Alexander
3 Pankratov, Denis
3 Pardubská, Dana
3 Păun, Gheorghe
3 Petersen, Holger
3 Pourmoradnasseri, Mozhgan
3 Qiu, Daowen
3 Renault, Marc P.
3 Rosén, Adi
3 Say, A. C. Cem
3 Scheithauer, Guntram
3 Sprock, Andreas
3 Štefáneková, Ivana
3 Steinová, Monika
3 Vrto, Imrich
3 Waack, Stephan
3 Wang, Hui
3 Wegener, Ingo
2 Ablaev, Farid M.
...and 456 more Authors
all top 5

Cited in 61 Serials

118 Theoretical Computer Science
41 Discrete Applied Mathematics
28 Information and Computation
26 Information Processing Letters
22 International Journal of Foundations of Computer Science
18 Journal of Computer and System Sciences
17 RAIRO. Theoretical Informatics and Applications
16 Algorithmica
15 Theory of Computing Systems
13 Journal of Discrete Algorithms
8 RAIRO. Theoretical Informatics and Applications
5 Kybernetika
5 Distributed Computing
4 Journal of Combinatorial Optimization
3 Artificial Intelligence
3 Discrete Mathematics
3 Information Sciences
3 Networks
3 RAIRO. Informatique Théorique et Applications
3 Lobachevskii Journal of Mathematics
2 Acta Informatica
2 Applied Mathematics and Computation
2 European Journal of Combinatorics
2 Optimization
2 Linear Algebra and its Applications
2 RAIRO. Operations Research
1 International Journal of Theoretical Physics
1 Annales de l’Institut Fourier
1 Automatica
1 Journal of Combinatorial Theory. Series A
1 The Journal of Symbolic Logic
1 Mathematica Slovaca
1 Mathematical Systems Theory
1 Opsearch
1 Annals of Pure and Applied Logic
1 Bulletin of the Iranian Mathematical Society
1 Journal of Complexity
1 Machine Learning
1 Computational Geometry
1 MSCS. Mathematical Structures in Computer Science
1 Computational Statistics
1 European Journal of Operational Research
1 International Journal of Computer Mathematics
1 The Australasian Journal of Combinatorics
1 Cybernetics and Systems Analysis
1 Computational Optimization and Applications
1 The Electronic Journal of Combinatorics
1 Acta Mathematica et Informatica Universitatis Ostraviensis
1 Journal of Scheduling
1 Fundamenta Informaticae
1 The Journal of Logic and Algebraic Programming
1 Natural Computing
1 ACM Journal of Experimental Algorithmics
1 Discrete Optimization
1 Sibirskie Èlektronnye Matematicheskie Izvestiya
1 Mathematics in Computer Science
1 Logical Methods in Computer Science
1 Discrete Mathematics, Algorithms and Applications
1 Advances in Operations Research
1 Fuzzy Information and Engineering
1 Journal of Membrane Computing

Citations by Year

Wikidata Timeline

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