Edit Profile (opens in new tab) Berman, Piotr Co-Author Distance Author ID: berman.piotr Published as: Berman, Piotr; Berman, P. Documents Indexed: 96 Publications since 1977, including 1 Book Co-Authors: 70 Co-Authors with 90 Joint Publications 3,243 Co-Co-Authors all top 5 Co-Authors 6 single-authored 23 DasGupta, Bhaskar 17 Karpinski, Marek 14 Raskhodnikova, Sofya 6 Murzabulatov, Meiram 6 Muthukrishnan, S. Muthu 6 Yaroslavtsev, Grigory 5 Kao, Ming-Yang 5 Lingas, Andrzej 5 Zelikovsky, Alexander Z. 4 Bhattacharyya, Arnab 4 Fujito, Toshihiro 3 Coulston, Chris 3 Nekrich, Yakov 3 Schnitger, Georg 2 Bafna, Vineet 2 Charikar, Moses S. 2 Fiat, Amos 2 Fürer, Martin 2 Fukuyama, Junichiro 2 Garay, Juan A. 2 Grigorescu, Elena 2 Karloff, Howard J. 2 Makarychev, Konstantin S. 2 Miller, Webb 2 Mubayi, Dhruv 2 Pelc, Andrzej 2 Ramaiyer, Viswanathan 2 Ramaswami, Suneeta 2 Sloan, Robert H. 2 Sontag, Eduardo D. 2 Turán, Gyorgy 2 Woodruff, David P. 2 Zhang, Yi 1 Ashley, Mary V. 1 Bar-Eli, Eldad 1 Berger-Wolf, Tanya Y. 1 Bertone, Paul 1 Blum, Avrim L. 1 Chaovalitwongse, Wanpracha Art 1 Das, Surajit K. 1 Demaine, Erik D. 1 Diks, Krzryztof 1 Gerstein, Mark 1 Gumucio, Deborah 1 Halpern, Joseph Yehuda 1 Hannenhalli, Sridhar 1 Hardison, Ross C. 1 Jeong, Jieun 1 Kahng, Andrew B. 1 Kaligounder, Lakshmi 1 Kasiviswanathan, Shiva Prasad 1 Kovoor, Nainan 1 Krysta, Piotr 1 Larmore, Lawrence L. 1 Pardalos, Panos M. 1 Plandowski, Wojciech 1 Rosén, Adi 1 Ruan, Ge 1 Rytter, Wojciech 1 Saks, Michael E. 1 Scott, Alexander D. 1 Snyder, Michael P. 1 Stojanović, Nikola 1 Tardos, Gábor 1 Tiuryn, Jerzy 1 Veeramachaneni, Vamsi 1 Vidhani, Devendra 1 Wang, Jie 1 Yan, Peiyuan 1 Zadimoghaddam, Morteza all top 5 Serials 6 Journal of Algorithms 5 Algorithmica 4 Discrete Applied Mathematics 3 Journal of Computer and System Sciences 3 Theoretical Computer Science 2 Information and Computation 2 SIAM Journal on Discrete Mathematics 2 Nordic Journal of Computing 2 ACM Transactions on Algorithms 1 Information Processing Letters 1 Mathematical Systems Theory 1 Networks 1 Combinatorica 1 SIAM Journal on Matrix Analysis and Applications 1 Random Structures & Algorithms 1 Distributed Computing 1 Theory of Computing Systems 1 Journal of Combinatorial Optimization 1 Journal of Discrete Algorithms all top 5 Fields 84 Computer science (68-XX) 26 Combinatorics (05-XX) 26 Operations research, mathematical programming (90-XX) 11 Biology and other natural sciences (92-XX) 5 Convex and discrete geometry (52-XX) 4 Order, lattices, ordered algebraic structures (06-XX) 3 Mathematical logic and foundations (03-XX) 3 Numerical analysis (65-XX) 3 Information and communication theory, circuits (94-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 77 Publications have been cited 798 times in 724 Documents Cited by ▼ Year ▼ A 2-approximation algorithm for the undirected feedback vertex set problem. Zbl 0932.68054 Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro 108 1999 On-line load balancing for related machines. Zbl 0954.68050 Berman, Piotr; Charikar, Moses; Karpinski, Marek 40 2000 On the complexity of approximating the independent set problem. Zbl 0804.90121 Berman, Piotr; Schnitger, Georg 37 1992 Improved approximations for the Steiner tree problem. Zbl 0820.68049 Berman, Piotr; Ramaiyer, Viswanathan 37 1994 \(8/7\)-approximation algorithm for \((1,2)\)-TSP. Zbl 1192.90158 Berman, Piotr; Karpinski, Marek 33 2006 1. 375-approximation algorithm for sorting by reversals. Zbl 1019.68817 Berman, Piotr; Hannenhalli, Sridhar; Karpinski, Marek 32 2002 On-line algorithms for Steiner tree problems. (Extended abstract). Zbl 0963.68152 Berman, Piotr; Coulston, Chris 31 1999 On approximation properties of the independent set problem for low degree graphs. Zbl 0916.68109 Berman, P.; Fujito, T. 24 1999 On complexity of regular languages in terms of finite automata. Zbl 0364.68057 Berman, Piotr; Lingas, Andrzej 24 1977 Approximating maximum independent set in bounded degree graphs. Zbl 0873.68163 Berman, Piotr; Fürer, Martin 19 1994 On approximation properties of the independent set problem for degree 3 graphs. Zbl 1502.68207 Berman, Piotr; Fujito, Toshihiro 18 1995 \(L_p\)-testing. Zbl 1315.68278 Berman, Piotr; Raskhodnikova, Sofya; Yaroslavtsev, Grigory 17 2014 A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs. Zbl 0972.68127 Berman, Piotr 17 2000 Efficient approximation algorithms for tiling and packing problems with rectangles. Zbl 0999.68248 Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S.; Ramaswami, Suneeta 16 2001 Approximation algorithms for spanner problems and directed Steiner forest. Zbl 1267.68317 Berman, Piotr; Bhattacharyya, Arnab; Makarychev, Konstantin; Raskhodnikova, Sofya; Yaroslavtsev, Grigory 16 2013 Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs (extended abstract). Zbl 1512.68189 Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro 16 1995 Tight approximability results for test set problems in bioinformatics. Zbl 1076.68113 Berman, Piotr; Dasgupta, Bhaskar; Kao, Ming-Yang 15 2005 On the complexity of pattern matching for highly compressed two-dimensional texts. Zbl 1059.68098 Berman, Piotr; Karpinski, Marek; Larmore, Lawrence L.; Plandowski, Wojciech; Rytter, Wojciech 12 2002 Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Zbl 1163.68045 Berman, Piotr; Dasgupta, Bhaskar; Sontag, Eduardo 12 2007 Cloture votes: \(n/4\)-resilient distributed consensus in \(t+1\) rounds. Zbl 0766.68004 Berman, Piotr; Garay, Juan A. 11 1993 A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs. Zbl 0966.68609 Berman, Piotr 11 2000 Online navigation in a room. Zbl 1321.68430 Bar-Eli, Eldad; Berman, Piotr; Fiat, Amos; Yan, Peiyuan 11 1994 Algorithms for the least distance problem. Zbl 0968.90501 Berman, Piotr; Kovoor, Nainan; Pardalos, Panos M. 10 1993 Faster approximation of distances in graphs. Zbl 1209.05238 Berman, Piotr; Kasiviswanathan, Shiva Prasad 10 2007 Randomized robot navigation algorithms. Zbl 0960.68593 Berman, Piotr; Blum, Avrim; Fiat, Amos; Karloff, Howard; Rosén, Adi; Saks, Michael 9 1996 Reliable broadcasting in logarithmic time with Byzantine link failures. Zbl 0866.68011 Berman, Piotr; Diks, Krzryztof; Pelc, Andrzej 9 1997 Tolerant testers of image properties. Zbl 1388.68281 Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya 9 2016 A competitive 3-server algorithm. Zbl 0800.68452 Berman, P.; Karloff, H.; Tardos, G. 9 1990 Improvements in throughout maximization for real-time scheduling. Zbl 1296.90040 Berman, Piotr; DasGupta, Bhaskar 9 2000 Improved approximations for the Steiner tree problem. Zbl 0829.68063 Berman, Piotr; Ramaiyer, Viswanathan 8 1992 Testing convexity of figures under the uniform distribution. Zbl 1387.68239 Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya 8 2016 Relationship between density and deterministic complexity of NP-complete languages. Zbl 0382.68068 Berman, Piotr 8 1978 \(O(1)\)-approximations for maximum movement problems. Zbl 1343.68306 Berman, Piotr; Demaine, Erik D.; Zadimoghaddam, Morteza 8 2011 Multi-phase algorithms for throughput maximization for real-time scheduling. Zbl 0991.90061 Berman, Piotr; Dasgupta, Bhaskar 8 2000 Complexities of efficient solutions of rectilinear polygon cover problems. Zbl 0869.68058 Berman, P.; DasGupta, B. 7 1997 The power and limitations of uniform samples in testing properties of figures. Zbl 1391.68106 Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya 7 2016 Computational complexity of some restricted instances of 3-SAT. Zbl 1111.68044 Berman, Piotr; Karpinski, Marek; Scott, Alexander D. 7 2007 Improved approximation for the directed spanner problem. Zbl 1332.68283 Berman, Piotr; Bhattacharyya, Arnab; Makarychev, Konstantin; Raskhodnikova, Sofya; Yaroslavtsev, Grigory 7 2011 Speed is more powerful than clairvoyance. Zbl 0946.68157 Berman, Piotr; Coulston, Chris 6 1999 1.25-approximation algorithm for Steiner tree problem with distances 1 and 2. Zbl 1253.68355 Berman, Piotr; Karpinski, Marek; Zelikovsky, Alexander 6 2009 On the complexity of approximating the independent set problem (extended abstract). Zbl 1492.68060 Berman, Piotr; Schnitger, Georg 6 1989 A linear-time algorithm for the 1-mismatch problem. Zbl 1497.68606 Stojanovic, Nikola; Berman, Piotr; Gumucio, Deborah; Hardison, Ross; Miller, Webb 6 1997 Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Zbl 1106.68432 Berman, Piotr; DasGupta, Bhaskar; Sontag, Eduardo 5 2004 Fast consensus in networks of bounded degree. Zbl 1282.68092 Berman, Piotr; Garay, Juan A. 5 1993 A note on sweeping automata. Zbl 0479.68081 Berman, Piotr 5 1980 Exact size of binary space partitionings and improved rectangle tiling algorithms. Zbl 1050.68145 Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S. 4 2002 Optimizing misdirection. Zbl 1094.68604 Berman, Piotr; Krysta, Piotr 4 2003 Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION. Zbl 1057.68646 Berman, Piotr; Karpinski, Marek 4 2002 Approximating minimum unsatisfiability of linear equations. Zbl 1254.68348 Berman, Piotr; Karpinski, Marek 3 2002 Simple approximation algorithm for nonoverlapping local alignments. Zbl 1092.68733 Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S. 3 2002 Improved approximation algorithms for rectangle tiling and packing. Zbl 1113.68635 Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S.; Ramaswami, Suneeta 3 2001 Approximation algorithms for MAX-MIN tiling. Zbl 1045.68149 Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S. 3 2003 Approximating the online set multicover problems via randomized winnowing. Zbl 1137.68061 Berman, Piotr; DasGupta, Bhaskar 3 2008 Approximating transitive reductions for directed networks. Zbl 1253.68354 Berman, Piotr; DasGupta, Bhaskar; Karpinski, Marek 3 2009 On constructing an optimal consensus clustering from multiple clusterings. Zbl 1184.68630 Berman, Piotr; Dasgupta, Bhaskar; Kao, Ming-Yang; Wang, Jie 3 2007 Finding sparser directed spanners. Zbl 1245.68246 Berman, Piotr; Raskhodnikova, Sofya; Ruan, Ge 3 2010 On approximation of the power-\(p\) and bottleneck Steiner trees. Zbl 0945.90046 Berman, Piotr; Zelikovsky, Alexander 2 2000 The \(T\)-join problem in sparse graphs: applications to phase assingment problem in VLSI mask layout. Zbl 1063.68612 Berman, Piotr; Kahng, Andrew B.; Vidhani, Devendra; Zelikovsky, Alexander 2 1999 Steiner transitive-closure spanners of low-dimensional posets. Zbl 1363.05094 Berman, Piotr; Bhattacharyya, Arnab; Grigorescu, Elena; Raskhodnikova, Sofya; Woodruff, David P.; Yaroslavtsev, Grigory 2 2014 On the computational complexity of measuring global stability of banking networks. Zbl 1307.91197 Berman, Piotr; DasGupta, Bhaskar; Kaligounder, Lakshmi; Karpinski, Marek 2 2014 On approximating four covering and packing problems. Zbl 1169.90017 Ashley, Mary; Berger-Wolf, Tanya; Berman, Piotr; Chaovalitwongse, Wanpracha; Dasgupta, Bhaskar; Kao, Ming-Yang 2 2009 Optimal trade-off for Merkle tree traversal. Zbl 1108.68047 Berman, Piotr; Karpinski, Marek; Nekrich, Yakov 2 2007 Steiner transitive-closure spanners of low-dimensional posets. Zbl 1333.68203 Berman, Piotr; Bhattacharyya, Arnab; Grigorescu, Elena; Raskhodnikova, Sofya; Woodruff, David P.; Yaroslavtsev, Grigory 2 2011 On the vehicle routing problem. Zbl 1161.68873 Berman, Piotr; Das, Surajit K. 2 2005 Primal-dual approximation algorithms for node-weighted network design in planar graphs. Zbl 1358.68318 Berman, Piotr; Yaroslavtsev, Grigory 2 2012 On the power of nondeterminism in dynamic logic. Zbl 0494.68032 Berman, Piotr; Halpern, Joseph Y.; Tiuryn, Jerzy 2 1982 Exact and approximation algorithms for geometric and capacitated set cover problems. Zbl 1252.68347 Berman, Piotr; Karpinski, Marek; Lingas, Andrzej 2 2012 On-line load balancing for related machines. Zbl 1497.68577 Berman, Piotr; Charikar, Moses; Karpinski, Marek 2 1997 The power and limitations of uniform samples in testing properties of figures. Zbl 1417.68225 Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya 1 2019 Testing convexity of figures under the uniform distribution. Zbl 1417.52002 Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya 1 2019 Slice and dice: a simple, improved approximate tiling recipe. Zbl 1093.68606 Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S. 1 2002 Aligning two fragmented sequences. Zbl 1014.92012 Veeramachaneni, Vamsi; Berman, Piotr; Miller, Webb 1 2003 A simple approximation algorithm for nonoverlapping local alignments (weighted independent sets of axis parallel rectangles). Zbl 1026.92022 Berman, Piotr; DasGupta, Bhaskar 1 2002 On the performance of the minimum degree ordering for Gaussian elimination. Zbl 0703.65016 Berman, Piotr; Schnitger, Georg 1 1990 A nearly parallel algorithm for the Voronoi diagram of a convex polygon. Zbl 0902.68202 Berman, Piotr; Lingas, Andrzej 1 1997 Applications of the linear matroid parity algorithm to approximating Steiner trees. Zbl 1185.68460 Berman, Piotr; Fürer, Martin; Zelikovsky, Alexander 1 2006 Exact and approximation algorithms for geometric and capacitated set cover problems. Zbl 1286.68461 Berman, Piotr; Karpinski, Marek; Lingas, Andrzej 1 2010 The power and limitations of uniform samples in testing properties of figures. Zbl 1417.68225 Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya 1 2019 Testing convexity of figures under the uniform distribution. Zbl 1417.52002 Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya 1 2019 Tolerant testers of image properties. Zbl 1388.68281 Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya 9 2016 Testing convexity of figures under the uniform distribution. Zbl 1387.68239 Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya 8 2016 The power and limitations of uniform samples in testing properties of figures. Zbl 1391.68106 Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya 7 2016 \(L_p\)-testing. Zbl 1315.68278 Berman, Piotr; Raskhodnikova, Sofya; Yaroslavtsev, Grigory 17 2014 Steiner transitive-closure spanners of low-dimensional posets. Zbl 1363.05094 Berman, Piotr; Bhattacharyya, Arnab; Grigorescu, Elena; Raskhodnikova, Sofya; Woodruff, David P.; Yaroslavtsev, Grigory 2 2014 On the computational complexity of measuring global stability of banking networks. Zbl 1307.91197 Berman, Piotr; DasGupta, Bhaskar; Kaligounder, Lakshmi; Karpinski, Marek 2 2014 Approximation algorithms for spanner problems and directed Steiner forest. Zbl 1267.68317 Berman, Piotr; Bhattacharyya, Arnab; Makarychev, Konstantin; Raskhodnikova, Sofya; Yaroslavtsev, Grigory 16 2013 Primal-dual approximation algorithms for node-weighted network design in planar graphs. Zbl 1358.68318 Berman, Piotr; Yaroslavtsev, Grigory 2 2012 Exact and approximation algorithms for geometric and capacitated set cover problems. Zbl 1252.68347 Berman, Piotr; Karpinski, Marek; Lingas, Andrzej 2 2012 \(O(1)\)-approximations for maximum movement problems. Zbl 1343.68306 Berman, Piotr; Demaine, Erik D.; Zadimoghaddam, Morteza 8 2011 Improved approximation for the directed spanner problem. Zbl 1332.68283 Berman, Piotr; Bhattacharyya, Arnab; Makarychev, Konstantin; Raskhodnikova, Sofya; Yaroslavtsev, Grigory 7 2011 Steiner transitive-closure spanners of low-dimensional posets. Zbl 1333.68203 Berman, Piotr; Bhattacharyya, Arnab; Grigorescu, Elena; Raskhodnikova, Sofya; Woodruff, David P.; Yaroslavtsev, Grigory 2 2011 Finding sparser directed spanners. Zbl 1245.68246 Berman, Piotr; Raskhodnikova, Sofya; Ruan, Ge 3 2010 Exact and approximation algorithms for geometric and capacitated set cover problems. Zbl 1286.68461 Berman, Piotr; Karpinski, Marek; Lingas, Andrzej 1 2010 1.25-approximation algorithm for Steiner tree problem with distances 1 and 2. Zbl 1253.68355 Berman, Piotr; Karpinski, Marek; Zelikovsky, Alexander 6 2009 Approximating transitive reductions for directed networks. Zbl 1253.68354 Berman, Piotr; DasGupta, Bhaskar; Karpinski, Marek 3 2009 On approximating four covering and packing problems. Zbl 1169.90017 Ashley, Mary; Berger-Wolf, Tanya; Berman, Piotr; Chaovalitwongse, Wanpracha; Dasgupta, Bhaskar; Kao, Ming-Yang 2 2009 Approximating the online set multicover problems via randomized winnowing. Zbl 1137.68061 Berman, Piotr; DasGupta, Bhaskar 3 2008 Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Zbl 1163.68045 Berman, Piotr; Dasgupta, Bhaskar; Sontag, Eduardo 12 2007 Faster approximation of distances in graphs. Zbl 1209.05238 Berman, Piotr; Kasiviswanathan, Shiva Prasad 10 2007 Computational complexity of some restricted instances of 3-SAT. Zbl 1111.68044 Berman, Piotr; Karpinski, Marek; Scott, Alexander D. 7 2007 On constructing an optimal consensus clustering from multiple clusterings. Zbl 1184.68630 Berman, Piotr; Dasgupta, Bhaskar; Kao, Ming-Yang; Wang, Jie 3 2007 Optimal trade-off for Merkle tree traversal. Zbl 1108.68047 Berman, Piotr; Karpinski, Marek; Nekrich, Yakov 2 2007 \(8/7\)-approximation algorithm for \((1,2)\)-TSP. Zbl 1192.90158 Berman, Piotr; Karpinski, Marek 33 2006 Applications of the linear matroid parity algorithm to approximating Steiner trees. Zbl 1185.68460 Berman, Piotr; Fürer, Martin; Zelikovsky, Alexander 1 2006 Tight approximability results for test set problems in bioinformatics. Zbl 1076.68113 Berman, Piotr; Dasgupta, Bhaskar; Kao, Ming-Yang 15 2005 On the vehicle routing problem. Zbl 1161.68873 Berman, Piotr; Das, Surajit K. 2 2005 Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Zbl 1106.68432 Berman, Piotr; DasGupta, Bhaskar; Sontag, Eduardo 5 2004 Optimizing misdirection. Zbl 1094.68604 Berman, Piotr; Krysta, Piotr 4 2003 Approximation algorithms for MAX-MIN tiling. Zbl 1045.68149 Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S. 3 2003 Aligning two fragmented sequences. Zbl 1014.92012 Veeramachaneni, Vamsi; Berman, Piotr; Miller, Webb 1 2003 1. 375-approximation algorithm for sorting by reversals. Zbl 1019.68817 Berman, Piotr; Hannenhalli, Sridhar; Karpinski, Marek 32 2002 On the complexity of pattern matching for highly compressed two-dimensional texts. Zbl 1059.68098 Berman, Piotr; Karpinski, Marek; Larmore, Lawrence L.; Plandowski, Wojciech; Rytter, Wojciech 12 2002 Exact size of binary space partitionings and improved rectangle tiling algorithms. Zbl 1050.68145 Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S. 4 2002 Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION. Zbl 1057.68646 Berman, Piotr; Karpinski, Marek 4 2002 Approximating minimum unsatisfiability of linear equations. Zbl 1254.68348 Berman, Piotr; Karpinski, Marek 3 2002 Simple approximation algorithm for nonoverlapping local alignments. Zbl 1092.68733 Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S. 3 2002 Slice and dice: a simple, improved approximate tiling recipe. Zbl 1093.68606 Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S. 1 2002 A simple approximation algorithm for nonoverlapping local alignments (weighted independent sets of axis parallel rectangles). Zbl 1026.92022 Berman, Piotr; DasGupta, Bhaskar 1 2002 Efficient approximation algorithms for tiling and packing problems with rectangles. Zbl 0999.68248 Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S.; Ramaswami, Suneeta 16 2001 Improved approximation algorithms for rectangle tiling and packing. Zbl 1113.68635 Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S.; Ramaswami, Suneeta 3 2001 On-line load balancing for related machines. Zbl 0954.68050 Berman, Piotr; Charikar, Moses; Karpinski, Marek 40 2000 A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs. Zbl 0972.68127 Berman, Piotr 17 2000 A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs. Zbl 0966.68609 Berman, Piotr 11 2000 Improvements in throughout maximization for real-time scheduling. Zbl 1296.90040 Berman, Piotr; DasGupta, Bhaskar 9 2000 Multi-phase algorithms for throughput maximization for real-time scheduling. Zbl 0991.90061 Berman, Piotr; Dasgupta, Bhaskar 8 2000 On approximation of the power-\(p\) and bottleneck Steiner trees. Zbl 0945.90046 Berman, Piotr; Zelikovsky, Alexander 2 2000 A 2-approximation algorithm for the undirected feedback vertex set problem. Zbl 0932.68054 Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro 108 1999 On-line algorithms for Steiner tree problems. (Extended abstract). Zbl 0963.68152 Berman, Piotr; Coulston, Chris 31 1999 On approximation properties of the independent set problem for low degree graphs. Zbl 0916.68109 Berman, P.; Fujito, T. 24 1999 Speed is more powerful than clairvoyance. Zbl 0946.68157 Berman, Piotr; Coulston, Chris 6 1999 The \(T\)-join problem in sparse graphs: applications to phase assingment problem in VLSI mask layout. Zbl 1063.68612 Berman, Piotr; Kahng, Andrew B.; Vidhani, Devendra; Zelikovsky, Alexander 2 1999 Reliable broadcasting in logarithmic time with Byzantine link failures. Zbl 0866.68011 Berman, Piotr; Diks, Krzryztof; Pelc, Andrzej 9 1997 Complexities of efficient solutions of rectilinear polygon cover problems. Zbl 0869.68058 Berman, P.; DasGupta, B. 7 1997 A linear-time algorithm for the 1-mismatch problem. Zbl 1497.68606 Stojanovic, Nikola; Berman, Piotr; Gumucio, Deborah; Hardison, Ross; Miller, Webb 6 1997 On-line load balancing for related machines. Zbl 1497.68577 Berman, Piotr; Charikar, Moses; Karpinski, Marek 2 1997 A nearly parallel algorithm for the Voronoi diagram of a convex polygon. Zbl 0902.68202 Berman, Piotr; Lingas, Andrzej 1 1997 Randomized robot navigation algorithms. Zbl 0960.68593 Berman, Piotr; Blum, Avrim; Fiat, Amos; Karloff, Howard; Rosén, Adi; Saks, Michael 9 1996 On approximation properties of the independent set problem for degree 3 graphs. Zbl 1502.68207 Berman, Piotr; Fujito, Toshihiro 18 1995 Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs (extended abstract). Zbl 1512.68189 Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro 16 1995 Improved approximations for the Steiner tree problem. Zbl 0820.68049 Berman, Piotr; Ramaiyer, Viswanathan 37 1994 Approximating maximum independent set in bounded degree graphs. Zbl 0873.68163 Berman, Piotr; Fürer, Martin 19 1994 Online navigation in a room. Zbl 1321.68430 Bar-Eli, Eldad; Berman, Piotr; Fiat, Amos; Yan, Peiyuan 11 1994 Cloture votes: \(n/4\)-resilient distributed consensus in \(t+1\) rounds. Zbl 0766.68004 Berman, Piotr; Garay, Juan A. 11 1993 Algorithms for the least distance problem. Zbl 0968.90501 Berman, Piotr; Kovoor, Nainan; Pardalos, Panos M. 10 1993 Fast consensus in networks of bounded degree. Zbl 1282.68092 Berman, Piotr; Garay, Juan A. 5 1993 On the complexity of approximating the independent set problem. Zbl 0804.90121 Berman, Piotr; Schnitger, Georg 37 1992 Improved approximations for the Steiner tree problem. Zbl 0829.68063 Berman, Piotr; Ramaiyer, Viswanathan 8 1992 A competitive 3-server algorithm. Zbl 0800.68452 Berman, P.; Karloff, H.; Tardos, G. 9 1990 On the performance of the minimum degree ordering for Gaussian elimination. Zbl 0703.65016 Berman, Piotr; Schnitger, Georg 1 1990 On the complexity of approximating the independent set problem (extended abstract). Zbl 1492.68060 Berman, Piotr; Schnitger, Georg 6 1989 On the power of nondeterminism in dynamic logic. Zbl 0494.68032 Berman, Piotr; Halpern, Joseph Y.; Tiuryn, Jerzy 2 1982 A note on sweeping automata. Zbl 0479.68081 Berman, Piotr 5 1980 Relationship between density and deterministic complexity of NP-complete languages. Zbl 0382.68068 Berman, Piotr 8 1978 On complexity of regular languages in terms of finite automata. Zbl 0364.68057 Berman, Piotr; Lingas, Andrzej 24 1977 all cited Publications top 5 cited Publications all top 5 Cited by 1,214 Authors 14 Saurabh, Saket 12 Berman, Piotr 11 DasGupta, Bhaskar 11 Epstein, Leah 11 Rawitz, Dror 10 Lin, Guohui 10 Pelc, Andrzej 10 Zhu, Daming 9 Halldórsson, Magnús Mar 9 Paschos, Vangelis Th. 9 Raskhodnikova, Sofya 8 Dias, Zanoni 8 Sgall, Jiří 8 Williamson, David P. 7 Bodlaender, Hans L. 7 Feige, Uriel 7 Fujito, Toshihiro 7 Kapoutsis, Christos A. 6 Choudhary, Pratibha 6 Fomin, Fedor V. 6 Geffert, Viliam 6 Jiang, Haitao 6 Kann, Viggo 6 Lintzmayer, Carla Negri 6 Lokshtanov, Daniel 6 Pighizzini, Giovanni 6 Zehavi, Meirav 5 Agrawal, Akanksha 5 Bar-Yehuda, Reuven 5 Bilò, Davide 5 Böhm, Martin 5 Chan, Timothy Moon-Yew 5 Chen, Zhizhong 5 Fernau, Henning 5 Fertin, Guillaume 5 Grigorescu, Elena 5 Guo, Jiong 5 Ito, Takehiro 5 Jansen, Bart M. P. 5 Královič, Richard 5 Megow, Nicole 5 Niedermeier, Rolf 5 Peleg, David 5 Raman, Venkatesh 5 Ravi, Ramamoorthi 5 Segev, Danny 5 Suchý, Ondřej 5 Tu, Jianhua 5 Wu, Weili 4 Abu-Affash, A. Karim 4 Carmi, Paz 4 Chakaravarthy, Venkatesan T. 4 Chakrabarty, Deeparnab 4 Chandran, L. Sunil 4 Chen, Jian-er 4 Chen, Yong 4 Choudhury, Anamitra Roy 4 Demange, Marc 4 Dinitz, Michael H. 4 Dósa, György 4 Eiben, Eduard 4 Fernandes, Cristina G. 4 Francis, Mathew C. 4 Gualà, Luciano 4 Hajiaghayi, Mohammad Taghi 4 Karpinski, Marek 4 Královič, Rastislav 4 Leucci, Stefano 4 Lohrey, Markus 4 Manurangsi, Pasin 4 Markarian, Christine 4 Meyer auf der Heide, Friedhelm 4 Mömke, Tobias 4 Nagamochi, Hiroshi 4 Naor, Joseph Seffi 4 Panigrahi, Debmalya 4 Proietti, Guido 4 Schmied, Richard 4 Tuza, Zsolt 4 Umboh, Seeun William 4 van Stee, Rob 4 Wang, Jianxin 4 Wang, Lusheng 4 Zelikovsky, Alexander Z. 4 Zhang, Zhao 3 Alexandrino, Alexsandro Oliveira 3 Angelopoulos, Spyros 3 Ashley, Mary V. 3 Banik, Aritra 3 Berger-Wolf, Tanya Y. 3 Bhore, Sujoy Kumar 3 Blais, Eric 3 Boppana, Ravi B. 3 Calinescu, Gruia 3 Censor-Hillel, Keren 3 Chaovalitwongse, Wanpracha Art 3 Chen, Lin 3 Chitnis, Rajesh Hemant 3 Crescenzi, Pierluigi 3 Dias, Ulisses ...and 1,114 more Authors all top 5 Cited in 94 Serials 97 Theoretical Computer Science 58 Algorithmica 42 Discrete Applied Mathematics 41 Information Processing Letters 28 Journal of Computer and System Sciences 21 Journal of Combinatorial Optimization 19 Information and Computation 18 SIAM Journal on Computing 16 SIAM Journal on Discrete Mathematics 16 Theory of Computing Systems 12 Mathematical Programming. Series A. Series B 11 European Journal of Operational Research 10 Journal of Scheduling 10 Journal of Discrete Algorithms 8 Operations Research Letters 8 Discrete Optimization 7 International Journal of Foundations of Computer Science 6 Discrete Mathematics 5 Networks 5 Computers & Operations Research 5 Computer Science Review 4 Annals of Operations Research 3 Combinatorica 3 Discrete & Computational Geometry 3 Random Structures & Algorithms 3 Computational Geometry 3 Computational Optimization and Applications 3 RAIRO. Operations Research 3 4OR 3 ACM Journal of Experimental Algorithmics 3 ACM Transactions on Algorithms 2 Applied Mathematics and Computation 2 Journal of Combinatorial Theory. Series B 2 Mathematical Systems Theory 2 Operations Research 2 Siberian Mathematical Journal 2 European Journal of Combinatorics 2 Applied Mathematics Letters 2 Journal of Cryptology 2 International Journal of Computational Geometry & Applications 2 Journal of Global Optimization 2 Automation and Remote Control 2 Distributed Computing 2 Computational Complexity 2 International Transactions in Operational Research 2 Journal of Graph Algorithms and Applications 2 CEJOR. Central European Journal of Operations Research 2 Optimization Letters 1 Artificial Intelligence 1 Computers & Mathematics with Applications 1 International Journal of Control 1 Journal of Mathematical Biology 1 Acta Mathematica 1 Advances in Mathematics 1 The Annals of Statistics 1 BIT 1 Information Sciences 1 International Journal of Game Theory 1 Journal of Optimization Theory and Applications 1 Opsearch 1 SIAM Journal on Numerical Analysis 1 Graphs and Combinatorics 1 Journal of Computer Science and Technology 1 Journal of Automated Reasoning 1 Asia-Pacific Journal of Operational Research 1 Japan Journal of Industrial and Applied Mathematics 1 International Journal of Algebra and Computation 1 MSCS. Mathematical Structures in Computer Science 1 Games and Economic Behavior 1 Historia Mathematica 1 SIAM Review 1 Bulletin of the American Mathematical Society. New Series 1 RAIRO. Informatique Théorique et Applications 1 Tatra Mountains Mathematical Publications 1 SIAM Journal on Scientific Computing 1 Annals of Mathematics and Artificial Intelligence 1 European Journal of Control 1 Optimization Methods & Software 1 Journal of the ACM 1 RAIRO. Theoretical Informatics and Applications 1 Journal of Systems Science and Complexity 1 Theory and Practice of Logic Programming 1 Advances in Complex Systems 1 Acta Numerica 1 Journal of Statistical Mechanics: Theory and Experiment 1 Journal of Industrial and Management Optimization 1 Journal of Zhejiang University. Science A 1 The European Physical Journal B. Condensed Matter and Complex Systems 1 Discrete Mathematics, Algorithms and Applications 1 Algorithms 1 Advances in Mathematical Physics 1 Science China. Information Sciences 1 RAIRO. Theoretical Informatics and Applications 1 Mathematical Foundations of Computing all top 5 Cited in 22 Fields 566 Computer science (68-XX) 238 Combinatorics (05-XX) 215 Operations research, mathematical programming (90-XX) 37 Biology and other natural sciences (92-XX) 22 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 14 Information and communication theory, circuits (94-XX) 10 Numerical analysis (65-XX) 7 Mathematical logic and foundations (03-XX) 7 Convex and discrete geometry (52-XX) 6 Order, lattices, ordered algebraic structures (06-XX) 3 Group theory and generalizations (20-XX) 3 Statistics (62-XX) 3 Systems theory; control (93-XX) 2 Number theory (11-XX) 2 Probability theory and stochastic processes (60-XX) 2 Quantum theory (81-XX) 2 Statistical mechanics, structure of matter (82-XX) 1 Commutative algebra (13-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Mechanics of particles and systems (70-XX) 1 Classical thermodynamics, heat transfer (80-XX) Citations by Year