×
Edit Profile (opens in new tab)

Berman, Piotr

Co-Author Distance
Author ID: berman.piotr Recent zbMATH articles by "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,272 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

80 Publications have been cited 939 times in 849 Documents Cited by ▼ Year ▼
A 2-approximation algorithm for the undirected feedback vertex set problem. Zbl 0932.68054
Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro
118
1999
On the complexity of approximating the independent set problem. Zbl 0804.90121
Berman, Piotr; Schnitger, Georg
45
1992
On-line load balancing for related machines. Zbl 0954.68050
Berman, Piotr; Charikar, Moses; Karpinski, Marek
41
2000
Improved approximations for the Steiner tree problem. Zbl 0820.68049
Berman, Piotr; Ramaiyer, Viswanathan
40
1994
\(8/7\)-approximation algorithm for \((1,2)\)-TSP. Zbl 1192.90158
Berman, Piotr; Karpinski, Marek
39
2006
1. 375-approximation algorithm for sorting by reversals. Zbl 1019.68817
Berman, Piotr; Hannenhalli, Sridhar; Karpinski, Marek
35
2002
On-line algorithms for Steiner tree problems. (Extended abstract). Zbl 0963.68152
Berman, Piotr; Coulston, Chris
35
1999
On complexity of regular languages in terms of finite automata. Zbl 0364.68057
Berman, Piotr; Lingas, Andrzej
28
1977
On approximation properties of the independent set problem for low degree graphs. Zbl 0916.68109
Berman, P.; Fujito, T.
26
1999
\(L_p\)-testing. Zbl 1315.68278
Berman, Piotr; Raskhodnikova, Sofya; Yaroslavtsev, Grigory
24
2014
A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs. Zbl 0972.68127
Berman, Piotr
24
2000
Relationship between density and deterministic complexity of NP-complete languages. Zbl 0382.68068
Berman, Piotr
24
1978
Approximating maximum independent set in bounded degree graphs. Zbl 0873.68163
Berman, Piotr; Fürer, Martin
23
1994
On approximation properties of the independent set problem for degree 3 graphs. Zbl 1502.68207
Berman, Piotr; Fujito, Toshihiro
21
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
20
1995
Approximation algorithms for spanner problems and directed Steiner forest. Zbl 1267.68317
Berman, Piotr; Bhattacharyya, Arnab; Makarychev, Konstantin; Raskhodnikova, Sofya; Yaroslavtsev, Grigory
17
2013
A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs. Zbl 0966.68609
Berman, Piotr
17
2000
Tight approximability results for test set problems in bioinformatics. Zbl 1076.68113
Berman, Piotr; Dasgupta, Bhaskar; Kao, Ming-Yang
16
2005
Efficient approximation algorithms for tiling and packing problems with rectangles. Zbl 0999.68248
Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S.; Ramaswami, Suneeta
16
2001
Cloture votes: \(n/4\)-resilient distributed consensus in \(t+1\) rounds. Zbl 0766.68004
Berman, Piotr; Garay, Juan A.
15
1993
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
13
2007
Faster approximation of distances in graphs. Zbl 1209.05238
Berman, Piotr; Kasiviswanathan, Shiva Prasad
13
2007
Improvements in throughout maximization for real-time scheduling. Zbl 1296.90040
Berman, Piotr; DasGupta, Bhaskar
12
2000
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
Online navigation in a room. Zbl 1321.68430
Bar-Eli, Eldad; Berman, Piotr; Fiat, Amos; Yan, Peiyuan
11
1994
Improved approximations for the Steiner tree problem. Zbl 0829.68063
Berman, Piotr; Ramaiyer, Viswanathan
10
1992
Reliable broadcasting in logarithmic time with Byzantine link failures. Zbl 0866.68011
Berman, Piotr; Diks, Krzryztof; Pelc, Andrzej
10
1997
Multi-phase algorithms for throughput maximization for real-time scheduling. Zbl 0991.90061
Berman, Piotr; Dasgupta, Bhaskar
10
2000
Algorithms for the least distance problem. Zbl 0968.90501
Berman, Piotr; Kovoor, Nainan; Pardalos, Panos M.
10
1993
A note on sweeping automata. Zbl 0479.68081
Berman, Piotr
10
1980
Tolerant testers of image properties. Zbl 1388.68281
Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya
9
2016
Randomized robot navigation algorithms. Zbl 0960.68593
Berman, Piotr; Blum, Avrim; Fiat, Amos; Karloff, Howard; Rosén, Adi; Saks, Michael
9
1996
A competitive 3-server algorithm. Zbl 0800.68452
Berman, P.; Karloff, H.; Tardos, G.
9
1990
A linear-time algorithm for the 1-mismatch problem. Zbl 1497.68606
Stojanovic, Nikola; Berman, Piotr; Gumucio, Deborah; Hardison, Ross; Miller, Webb
9
1997
\(O(1)\)-approximations for maximum movement problems. Zbl 1343.68306
Berman, Piotr; Demaine, Erik D.; Zadimoghaddam, Morteza
8
2011
Testing convexity of figures under the uniform distribution. Zbl 1387.68239
Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya
8
2016
Fast consensus in networks of bounded degree. Zbl 1282.68092
Berman, Piotr; Garay, Juan A.
8
1993
The power and limitations of uniform samples in testing properties of figures. Zbl 1391.68106
Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya
7
2016
Improved approximation for the directed spanner problem. Zbl 1332.68283
Berman, Piotr; Bhattacharyya, Arnab; Makarychev, Konstantin; Raskhodnikova, Sofya; Yaroslavtsev, Grigory
7
2011
Complexities of efficient solutions of rectilinear polygon cover problems. Zbl 0869.68058
Berman, P.; DasGupta, B.
7
1997
Speed is more powerful than clairvoyance. Zbl 0946.68157
Berman, Piotr; Coulston, Chris
7
1999
On the power of nondeterminism in dynamic logic. Zbl 0494.68032
Berman, Piotr; Halpern, Joseph Y.; Tiuryn, Jerzy
7
1982
Computational complexity of some restricted instances of 3-SAT. Zbl 1111.68044
Berman, Piotr; Karpinski, Marek; Scott, Alexander D.
7
2007
On the complexity of approximating the independent set problem (extended abstract). Zbl 1492.68060
Berman, Piotr; Schnitger, Georg
6
1989
Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION. Zbl 1057.68646
Berman, Piotr; Karpinski, Marek
6
2002
1.25-approximation algorithm for Steiner tree problem with distances 1 and 2. Zbl 1253.68355
Berman, Piotr; Karpinski, Marek; Zelikovsky, Alexander
6
2009
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
Approximating minimum unsatisfiability of linear equations. Zbl 1254.68348
Berman, Piotr; Karpinski, Marek
5
2002
Approximating transitive reductions for directed networks. Zbl 1253.68354
Berman, Piotr; DasGupta, Bhaskar; Karpinski, Marek
5
2009
Primal-dual approximation algorithms for node-weighted network design in planar graphs. Zbl 1358.68318
Berman, Piotr; Yaroslavtsev, Grigory
4
2012
Optimizing misdirection. Zbl 1094.68604
Berman, Piotr; Krysta, Piotr
4
2003
Exact size of binary space partitionings and improved rectangle tiling algorithms. Zbl 1050.68145
Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S.
4
2002
Finding sparser directed spanners. Zbl 1245.68246
Berman, Piotr; Raskhodnikova, Sofya; Ruan, Ge
4
2010
The power and limitations of uniform samples in testing properties of figures. Zbl 1417.68225
Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya
3
2019
Steiner transitive-closure spanners of low-dimensional posets. Zbl 1363.05094
Berman, Piotr; Bhattacharyya, Arnab; Grigorescu, Elena; Raskhodnikova, Sofya; Woodruff, David P.; Yaroslavtsev, Grigory
3
2014
On approximation of the power-\(p\) and bottleneck Steiner trees. Zbl 0945.90046
Berman, Piotr; Zelikovsky, Alexander
3
2000
On-line load balancing for related machines. Zbl 1497.68577
Berman, Piotr; Charikar, Moses; Karpinski, Marek
3
1997
Approximation algorithms for MAX-MIN tiling. Zbl 1045.68149
Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S.
3
2003
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
Approximating the online set multicover problems via randomized winnowing. Zbl 1137.68061
Berman, Piotr; DasGupta, Bhaskar
3
2008
Optimal trade-off for Merkle tree traversal. Zbl 1108.68047
Berman, Piotr; Karpinski, Marek; Nekrich, Yakov
3
2007
On constructing an optimal consensus clustering from multiple clusterings. Zbl 1184.68630
Berman, Piotr; Dasgupta, Bhaskar; Kao, Ming-Yang; Wang, Jie
3
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
Exact and approximation algorithms for geometric and capacitated set cover problems. Zbl 1252.68347
Berman, Piotr; Karpinski, Marek; Lingas, Andrzej
2
2012
On the computational complexity of measuring global stability of banking networks. Zbl 1307.91197
Berman, Piotr; DasGupta, Bhaskar; Kaligounder, Lakshmi; Karpinski, Marek
2
2014
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
On the vehicle routing problem. Zbl 1161.68873
Berman, Piotr; Das, Surajit K.
2
2005
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
Testing convexity of figures under the uniform distribution. Zbl 1417.52002
Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya
1
2019
A nearly parallel algorithm for the Voronoi diagram of a convex polygon. Zbl 0902.68202
Berman, Piotr; Lingas, Andrzej
1
1997
Complexity of the theory of atomless Boolean algebras. Zbl 0421.03028
Berman, Piotr
1
1979
A simple approximation algorithm for nonoverlapping local alignments (weighted independent sets of axis parallel rectangles). Zbl 1026.92022
Berman, Piotr; DasGupta, Bhaskar
1
2002
Aligning two fragmented sequences. Zbl 1014.92012
Veeramachaneni, Vamsi; Berman, Piotr; Miller, Webb
1
2003
Slice and dice: a simple, improved approximate tiling recipe. Zbl 1093.68606
Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S.
1
2002
On the performance of the minimum degree ordering for Gaussian elimination. Zbl 0703.65016
Berman, Piotr; Schnitger, Georg
1
1990
Deterministic dynamic logic of recursive programs is weaker than dynamic logic. Zbl 0545.68020
Berman, Piotr
1
1983
Tolerant testers of image properties. Zbl 07758431
Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya
1
2022
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
Tolerant testers of image properties. Zbl 07758431
Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya
1
2022
The power and limitations of uniform samples in testing properties of figures. Zbl 1417.68225
Berman, Piotr; Murzabulatov, Meiram; Raskhodnikova, Sofya
3
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
24
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
3
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
17
2013
Primal-dual approximation algorithms for node-weighted network design in planar graphs. Zbl 1358.68318
Berman, Piotr; Yaroslavtsev, Grigory
4
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
4
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
5
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
13
2007
Faster approximation of distances in graphs. Zbl 1209.05238
Berman, Piotr; Kasiviswanathan, Shiva Prasad
13
2007
Computational complexity of some restricted instances of 3-SAT. Zbl 1111.68044
Berman, Piotr; Karpinski, Marek; Scott, Alexander D.
7
2007
Optimal trade-off for Merkle tree traversal. Zbl 1108.68047
Berman, Piotr; Karpinski, Marek; Nekrich, Yakov
3
2007
On constructing an optimal consensus clustering from multiple clusterings. Zbl 1184.68630
Berman, Piotr; Dasgupta, Bhaskar; Kao, Ming-Yang; Wang, Jie
3
2007
\(8/7\)-approximation algorithm for \((1,2)\)-TSP. Zbl 1192.90158
Berman, Piotr; Karpinski, Marek
39
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
16
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
35
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
Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION. Zbl 1057.68646
Berman, Piotr; Karpinski, Marek
6
2002
Approximating minimum unsatisfiability of linear equations. Zbl 1254.68348
Berman, Piotr; Karpinski, Marek
5
2002
Exact size of binary space partitionings and improved rectangle tiling algorithms. Zbl 1050.68145
Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S.
4
2002
Simple approximation algorithm for nonoverlapping local alignments. Zbl 1092.68733
Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S.
3
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
Slice and dice: a simple, improved approximate tiling recipe. Zbl 1093.68606
Berman, Piotr; DasGupta, Bhaskar; Muthukrishnan, S.
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
41
2000
A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs. Zbl 0972.68127
Berman, Piotr
24
2000
A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs. Zbl 0966.68609
Berman, Piotr
17
2000
Improvements in throughout maximization for real-time scheduling. Zbl 1296.90040
Berman, Piotr; DasGupta, Bhaskar
12
2000
Multi-phase algorithms for throughput maximization for real-time scheduling. Zbl 0991.90061
Berman, Piotr; Dasgupta, Bhaskar
10
2000
On approximation of the power-\(p\) and bottleneck Steiner trees. Zbl 0945.90046
Berman, Piotr; Zelikovsky, Alexander
3
2000
A 2-approximation algorithm for the undirected feedback vertex set problem. Zbl 0932.68054
Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro
118
1999
On-line algorithms for Steiner tree problems. (Extended abstract). Zbl 0963.68152
Berman, Piotr; Coulston, Chris
35
1999
On approximation properties of the independent set problem for low degree graphs. Zbl 0916.68109
Berman, P.; Fujito, T.
26
1999
Speed is more powerful than clairvoyance. Zbl 0946.68157
Berman, Piotr; Coulston, Chris
7
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
10
1997
A linear-time algorithm for the 1-mismatch problem. Zbl 1497.68606
Stojanovic, Nikola; Berman, Piotr; Gumucio, Deborah; Hardison, Ross; Miller, Webb
9
1997
Complexities of efficient solutions of rectilinear polygon cover problems. Zbl 0869.68058
Berman, P.; DasGupta, B.
7
1997
On-line load balancing for related machines. Zbl 1497.68577
Berman, Piotr; Charikar, Moses; Karpinski, Marek
3
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
21
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
20
1995
Improved approximations for the Steiner tree problem. Zbl 0820.68049
Berman, Piotr; Ramaiyer, Viswanathan
40
1994
Approximating maximum independent set in bounded degree graphs. Zbl 0873.68163
Berman, Piotr; Fürer, Martin
23
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.
15
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.
8
1993
On the complexity of approximating the independent set problem. Zbl 0804.90121
Berman, Piotr; Schnitger, Georg
45
1992
Improved approximations for the Steiner tree problem. Zbl 0829.68063
Berman, Piotr; Ramaiyer, Viswanathan
10
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
Deterministic dynamic logic of recursive programs is weaker than dynamic logic. Zbl 0545.68020
Berman, Piotr
1
1983
On the power of nondeterminism in dynamic logic. Zbl 0494.68032
Berman, Piotr; Halpern, Joseph Y.; Tiuryn, Jerzy
7
1982
A note on sweeping automata. Zbl 0479.68081
Berman, Piotr
10
1980
Complexity of the theory of atomless Boolean algebras. Zbl 0421.03028
Berman, Piotr
1
1979
Relationship between density and deterministic complexity of NP-complete languages. Zbl 0382.68068
Berman, Piotr
24
1978
On complexity of regular languages in terms of finite automata. Zbl 0364.68057
Berman, Piotr; Lingas, Andrzej
28
1977
all cited Publications top 5 cited Publications
all top 5

Cited by 1,366 Authors

18 Saurabh, Saket
14 Rawitz, Dror
13 Lin, Guohui
12 Berman, Piotr
12 Zhu, Daming
11 DasGupta, Bhaskar
11 Epstein, Leah
11 Halldórsson, Magnús Mar
11 Pelc, Andrzej
10 Feige, Uriel
10 Jiang, Haitao
10 Williamson, David P.
9 Fujito, Toshihiro
9 Lokshtanov, Daniel
9 Paschos, Vangelis Th.
9 Raskhodnikova, Sofya
8 Chen, Zhizhong
8 Dias, Zanoni
8 Sgall, Jiří
8 Wang, Lusheng
8 Zehavi, Meirav
7 Bodlaender, Hans L.
7 Choudhary, Pratibha
7 Fomin, Fedor V.
7 Guo, Jiong
7 Kapoutsis, Christos A.
7 Lintzmayer, Carla Negri
6 Agrawal, Akanksha
6 Bar-Yehuda, Reuven
6 Fernandes, Cristina G.
6 Geffert, Viliam
6 Jansen, Bart M. P.
6 Kann, Viggo
6 Naor, Joseph Seffi
6 Peleg, David
6 Pighizzini, Giovanni
6 Raman, Venkatesh
6 Ravi, Ramamoorthi
6 Wang, Jianxin
6 Zhu, Binhai
5 Bilò, Davide
5 Blais, Eric
5 Böhm, Martin
5 Censor-Hillel, Keren
5 Chakaravarthy, Venkatesan T.
5 Chakrabarty, Deeparnab
5 Chan, Timothy Moon-Yew
5 Chen, Yong
5 Dinitz, Michael H.
5 Feng, Qilong
5 Fernau, Henning
5 Fertin, Guillaume
5 Goemans, Michel Xavier
5 Grigorescu, Elena
5 Hajiaghayi, Mohammad Taghi
5 Ito, Takehiro
5 Karpinski, Marek
5 Královič, Richard
5 Megow, Nicole
5 Niedermeier, Rolf
5 Panigrahi, Debmalya
5 Panolan, Fahad
5 Segev, Danny
5 Suchý, Ondřej
5 Tu, Jianhua
5 Wu, Weili
5 Yamakami, Tomoyuki
5 Zhang, Zhao
4 Abu-Affash, A. Karim
4 Banik, Aritra
4 Boppana, Ravi B.
4 Calinescu, Gruia
4 Carmi, Paz
4 Chandran, L. Sunil
4 Chen, Jian-er
4 Choudhury, Anamitra Roy
4 Demange, Marc
4 Dory, Michal
4 Dósa, György
4 Du, Ding-Zhu
4 Eiben, Eduard
4 Fraigniaud, Pierre
4 Francis, Mathew C.
4 Fu, Bin
4 Gualà, Luciano
4 Gupta, Anupam
4 Im, Sungjin
4 Královič, Rastislav
4 Lam, Tak-Wah
4 Leucci, Stefano
4 Lin, Mugang
4 Lohrey, Markus
4 Ma, Bin
4 Mahaney, Stephen R.
4 Manurangsi, Pasin
4 Markarian, Christine
4 Meyer auf der Heide, Friedhelm
4 Misra, Pranabendu
4 Miyano, Eiji
4 Mömke, Tobias
...and 1,266 more Authors
all top 5

Cited in 99 Serials

111 Theoretical Computer Science
61 Algorithmica
46 Discrete Applied Mathematics
45 Information Processing Letters
39 Journal of Computer and System Sciences
21 Information and Computation
21 Journal of Combinatorial Optimization
18 SIAM Journal on Computing
16 SIAM Journal on Discrete Mathematics
16 Theory of Computing Systems
13 Mathematical Programming. Series A. Series B
11 European Journal of Operational Research
11 Journal of Discrete Algorithms
10 Journal of Scheduling
9 Operations Research Letters
8 Networks
8 Discrete Optimization
7 International Journal of Foundations of Computer Science
6 Discrete Mathematics
6 Computers & Operations Research
5 Annals of Operations Research
5 Random Structures & Algorithms
5 Computer Science Review
3 European Journal of Combinatorics
3 Combinatorica
3 Discrete & Computational Geometry
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 Asia-Pacific Journal of Operational Research
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 Graph Theory
1 Journal of Optimization Theory and Applications
1 Opsearch
1 SIAM Journal on Numerical Analysis
1 Graphs and Combinatorics
1 Journal of Complexity
1 Journal of Computer Science and Technology
1 Journal of Automated Reasoning
1 Neural Networks
1 Japan Journal of Industrial and Applied Mathematics
1 International Journal of Algebra and Computation
1 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 Journal of Combinatorial Designs
1 The Journal of Artificial Intelligence Research (JAIR)
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

673 Computer science (68-XX)
268 Combinatorics (05-XX)
251 Operations research, mathematical programming (90-XX)
43 Biology and other natural sciences (92-XX)
28 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
25 Mathematical logic and foundations (03-XX)
17 Information and communication theory, circuits (94-XX)
10 Numerical analysis (65-XX)
7 Convex and discrete geometry (52-XX)
6 Order, lattices, ordered algebraic structures (06-XX)
4 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