×

zbMATH — the first resource for mathematics

Farach-Colton, Martin

Compute Distance To:
Author ID: farach-colton.martin Recent zbMATH articles by "Farach-Colton, Martin"
Published as: Farach-Colton, M.; Farach-Colton, Martin; Farach-Colton, Martín
Documents Indexed: 57 Publications since 1998, including 5 Books

Publications by Year

Citations contained in zbMATH

35 Publications have been cited 426 times in 362 Documents Cited by Year
The LCA problem revisited. Zbl 0959.68133
Bender, Michael A.; Farach-Colton, Martín
145
2000
Lowest common ancestors in trees and directed acyclic graphs. Zbl 1085.68103
Bender, Michael A.; Farach-Colton, Martín; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel
40
2005
On the sorting-complexity of suffix tree construction. Zbl 1094.68694
Farach-Colton, Martin; Ferragina, Paolo; Muthukrishnan, S.
39
2000
The level ancestor problem simplified. Zbl 1068.68047
Bender, Michael A.; Farach-Colton, Martín
28
2004
Finding frequent items in data streams. Zbl 1057.68600
Charikar, Moses; Chen, Kevin; Farach-Colton, Martin
24
2002
Two simplified algorithms for maintaining order in a list. Zbl 1019.68527
Bender, Michael A.; Cole, Richard; Demaine, Erik D.; Farach-Colton, Martin; Zito, Jack
22
2002
Finding frequent items in data streams. Zbl 1071.68020
Charikar, Moses; Chen, Kevin; Farach-Colton, Martin
17
2004
An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees. Zbl 0976.68081
Cole, Richard; Farach-Colton, Martin; Hariharan, Ramesh; Przytycka, Teresa; Thorup, Mikkel
16
2000
Cache-oblivious B-trees. Zbl 1092.68028
Bender, Michael A.; Demaine, Erik D.; Farach-Colton, Martin
15
2005
Fast and compact regular expression matching. Zbl 1155.68022
Bille, Philip; Farach-Colton, Martin
9
2008
The level ancestor problem simplified. Zbl 1059.68563
Bender, Michael A.; Farach-Colton, Martín
8
2002
Reallocation problems in scheduling. Zbl 1322.68029
Bender, Michael A.; Farach-Colton, Martin; Fekete, Sándor P.; Fineman, Jeremy T.; Gilbert, Seth
5
2015
Sensor network gossiping or how to break the broadcast lower bound. Zbl 1193.68028
Farach-Colton, Martín; Mosteiro, Miguel A.
5
2007
Optimal spaced seeds for faster approximate string matching. Zbl 1123.68119
Farach-Colton, Martin; Landau, Gad M.; Sahinalp, S. Cenk; Tsur, Dekel
5
2007
Ordinal embeddings of minimum relaxation, general properties, trees, and ultrametrics. Zbl 1297.68079
Alon, Noga; Bădoiu, Mihai; Demaine, Erik D.; Farach-Colton, Martin; Hajiaghayi, MohammadTaghi; Sidiropoulos, Anastasios
5
2005
Optimal parallel two dimensional text searching on a CREW PRAM. Zbl 0917.68049
Amir, Amihood; Benson, Gary; Farach-Colton, Martin
5
1998
Undiscretized dynamic programming: Faster algorithms for facility location and related problems on trees. Zbl 1093.68628
Shah, Rahul; Farach-Colton, Martin
4
2002
Fault-tolerant aggregation: flow-updating meets mass-distribution. Zbl 1420.68022
Almeida, Paulo Sérgio; Baquero, Carlos; Farach-Colton, Martín; Jesus, Paulo; Mosteiro, Miguel A.
3
2017
Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. Zbl 1445.68182
Alon, Noga; Bădoiu, Mihai; Demaine, Erik D.; Farach-Colton, Martin; Hajiaghayi, Mohammadtaghi; Sidiropoulos, Anastasios
3
2008
Lower bounds for clear transmissions in radio networks. Zbl 1145.68324
Farach-Colton, Martín; Fernandes, Rohan J.; Mosteiro, Miguel A.
3
2006
Optimal spaced seeds for faster approximate string matching. Zbl 1081.68674
Farach-Colton, Martin; Landau, Gad M.; Sahinalp, S. Cenk; Tsur, Dekel
3
2005
Fast, fair, and frugal bandwidth allocation in ATM networks. Zbl 0934.68013
Bartal, Yair; Farach-Colton, Martin; Yooseph, Shibu; Zhang, Lisa
3
1999
Forty years of text indexing. Zbl 1381.68067
Apostolico, Alberto; Crochemore, Maxime; Farach-Colton, Martin; Galil, Zvi; Muthukrishnan, S.
2
2013
Bootstrapping a hop-optimal network in the weak sensor model. Zbl 1298.68040
Farach-Colton, Martin; Fernandes, Rohan J.; Mosteiro, Miguel A.
2
2009
A linear delay algorithm for building concept lattices. Zbl 1143.68602
Farach-Colton, Martin; Huang, Yang
2
2008
Initializing sensor networks of non-uniform density in the weak sensor model. Zbl 1209.68045
Farach-Colton, Martín; Mosteiro, Miguel A.
2
2007
Efficient tree layout in a multilevel memory hierarchy. Zbl 1019.68525
Bender, Michael A.; Demaine, Erik D.; Farach-Colton, Martin
2
2002
Scanning and traversing: Maintaining data for traversals in a memory hierarchy. Zbl 1019.68526
Bender, Michael A.; Cole, Richard; Demaine, Erik D.; Farach-Colton, Martin
2
2002
Parallel lookups in string indexes. Zbl 1397.68237
Christiansen, Anders Roy; Farach-Colton, Martín
1
2016
On the complexity of computing prime tables. Zbl 1417.68066
Farach-Colton, Martín; Tsai, Meng-Tsung
1
2015
Exact sublinear binomial sampling. Zbl 1331.68278
Farach-Colton, Martín; Tsai, Meng-Tsung
1
2013
Optimal memory-aware sensor network gossiping (or how to break the broadcast lower bound). Zbl 1259.68016
Farach-Colton, Martín; Anta, Antonio Fernández; Mosteiro, Miguel A.
1
2013
INSERTION SORT is \(O(n \log n)\). Zbl 1107.68034
Bender, Michael A.; Farach-Colton, Martin; Mosteiro, Miguel A.
1
2006
Bootstrapping a hop-optimal network in the weak sensor model. Zbl 1142.90338
Farach-Colton, Martín; Fernandes, Rohan J.; Mosteiro, Miguel A.
1
2005
Fast, fair and frugal bandwidth allocation in ATM networks. Zbl 0994.68003
Bartal, Y.; Farach-Colton, M.; Yooseph, S.; Zhang, L.
1
2002
Fault-tolerant aggregation: flow-updating meets mass-distribution. Zbl 1420.68022
Almeida, Paulo Sérgio; Baquero, Carlos; Farach-Colton, Martín; Jesus, Paulo; Mosteiro, Miguel A.
3
2017
Parallel lookups in string indexes. Zbl 1397.68237
Christiansen, Anders Roy; Farach-Colton, Martín
1
2016
Reallocation problems in scheduling. Zbl 1322.68029
Bender, Michael A.; Farach-Colton, Martin; Fekete, Sándor P.; Fineman, Jeremy T.; Gilbert, Seth
5
2015
On the complexity of computing prime tables. Zbl 1417.68066
Farach-Colton, Martín; Tsai, Meng-Tsung
1
2015
Forty years of text indexing. Zbl 1381.68067
Apostolico, Alberto; Crochemore, Maxime; Farach-Colton, Martin; Galil, Zvi; Muthukrishnan, S.
2
2013
Exact sublinear binomial sampling. Zbl 1331.68278
Farach-Colton, Martín; Tsai, Meng-Tsung
1
2013
Optimal memory-aware sensor network gossiping (or how to break the broadcast lower bound). Zbl 1259.68016
Farach-Colton, Martín; Anta, Antonio Fernández; Mosteiro, Miguel A.
1
2013
Bootstrapping a hop-optimal network in the weak sensor model. Zbl 1298.68040
Farach-Colton, Martin; Fernandes, Rohan J.; Mosteiro, Miguel A.
2
2009
Fast and compact regular expression matching. Zbl 1155.68022
Bille, Philip; Farach-Colton, Martin
9
2008
Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. Zbl 1445.68182
Alon, Noga; Bădoiu, Mihai; Demaine, Erik D.; Farach-Colton, Martin; Hajiaghayi, Mohammadtaghi; Sidiropoulos, Anastasios
3
2008
A linear delay algorithm for building concept lattices. Zbl 1143.68602
Farach-Colton, Martin; Huang, Yang
2
2008
Sensor network gossiping or how to break the broadcast lower bound. Zbl 1193.68028
Farach-Colton, Martín; Mosteiro, Miguel A.
5
2007
Optimal spaced seeds for faster approximate string matching. Zbl 1123.68119
Farach-Colton, Martin; Landau, Gad M.; Sahinalp, S. Cenk; Tsur, Dekel
5
2007
Initializing sensor networks of non-uniform density in the weak sensor model. Zbl 1209.68045
Farach-Colton, Martín; Mosteiro, Miguel A.
2
2007
Lower bounds for clear transmissions in radio networks. Zbl 1145.68324
Farach-Colton, Martín; Fernandes, Rohan J.; Mosteiro, Miguel A.
3
2006
INSERTION SORT is \(O(n \log n)\). Zbl 1107.68034
Bender, Michael A.; Farach-Colton, Martin; Mosteiro, Miguel A.
1
2006
Lowest common ancestors in trees and directed acyclic graphs. Zbl 1085.68103
Bender, Michael A.; Farach-Colton, Martín; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel
40
2005
Cache-oblivious B-trees. Zbl 1092.68028
Bender, Michael A.; Demaine, Erik D.; Farach-Colton, Martin
15
2005
Ordinal embeddings of minimum relaxation, general properties, trees, and ultrametrics. Zbl 1297.68079
Alon, Noga; Bădoiu, Mihai; Demaine, Erik D.; Farach-Colton, Martin; Hajiaghayi, MohammadTaghi; Sidiropoulos, Anastasios
5
2005
Optimal spaced seeds for faster approximate string matching. Zbl 1081.68674
Farach-Colton, Martin; Landau, Gad M.; Sahinalp, S. Cenk; Tsur, Dekel
3
2005
Bootstrapping a hop-optimal network in the weak sensor model. Zbl 1142.90338
Farach-Colton, Martín; Fernandes, Rohan J.; Mosteiro, Miguel A.
1
2005
The level ancestor problem simplified. Zbl 1068.68047
Bender, Michael A.; Farach-Colton, Martín
28
2004
Finding frequent items in data streams. Zbl 1071.68020
Charikar, Moses; Chen, Kevin; Farach-Colton, Martin
17
2004
Finding frequent items in data streams. Zbl 1057.68600
Charikar, Moses; Chen, Kevin; Farach-Colton, Martin
24
2002
Two simplified algorithms for maintaining order in a list. Zbl 1019.68527
Bender, Michael A.; Cole, Richard; Demaine, Erik D.; Farach-Colton, Martin; Zito, Jack
22
2002
The level ancestor problem simplified. Zbl 1059.68563
Bender, Michael A.; Farach-Colton, Martín
8
2002
Undiscretized dynamic programming: Faster algorithms for facility location and related problems on trees. Zbl 1093.68628
Shah, Rahul; Farach-Colton, Martin
4
2002
Efficient tree layout in a multilevel memory hierarchy. Zbl 1019.68525
Bender, Michael A.; Demaine, Erik D.; Farach-Colton, Martin
2
2002
Scanning and traversing: Maintaining data for traversals in a memory hierarchy. Zbl 1019.68526
Bender, Michael A.; Cole, Richard; Demaine, Erik D.; Farach-Colton, Martin
2
2002
Fast, fair and frugal bandwidth allocation in ATM networks. Zbl 0994.68003
Bartal, Y.; Farach-Colton, M.; Yooseph, S.; Zhang, L.
1
2002
The LCA problem revisited. Zbl 0959.68133
Bender, Michael A.; Farach-Colton, Martín
145
2000
On the sorting-complexity of suffix tree construction. Zbl 1094.68694
Farach-Colton, Martin; Ferragina, Paolo; Muthukrishnan, S.
39
2000
An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees. Zbl 0976.68081
Cole, Richard; Farach-Colton, Martin; Hariharan, Ramesh; Przytycka, Teresa; Thorup, Mikkel
16
2000
Fast, fair, and frugal bandwidth allocation in ATM networks. Zbl 0934.68013
Bartal, Yair; Farach-Colton, Martin; Yooseph, Shibu; Zhang, Lisa
3
1999
Optimal parallel two dimensional text searching on a CREW PRAM. Zbl 0917.68049
Amir, Amihood; Benson, Gary; Farach-Colton, Martin
5
1998
all top 5

Cited by 637 Authors

15 Navarro, Gonzalo
10 Iliopoulos, Costas S.
10 Inenaga, Shunsuke
9 Hon, Wing-Kai
9 Wang, Haitao
8 Bannai, Hideo
8 Mosteiro, Miguel A.
8 Park, Kunsoo
8 Shah, Rahul
7 Amir, Amihood
7 Bille, Philip
7 Pissis, Solon P.
7 Radoszewski, Jakub
7 Sung, Wing-Kin
7 Takeda, Masayuki
7 Thankachan, Sharma V.
6 Chao, Kunmao
6 Crochemore, Maxime
6 Durocher, Stephane
6 Gawrychowski, Paweł
6 Gørtz, Inge Li
6 Kim, Dong Kyue
6 Kociumaka, Tomasz
6 Lewenstein, Moshe
6 Nekrich, Yakov
6 Rahman, Mohammad Sohel
6 Waleń, Tomasz
5 Fischer, Johannes
5 Ganguly, Sumit
5 Jansson, Jesper
5 Landau, Gad M.
5 Porat, Ely
5 Rytter, Wojciech
5 Sadakane, Kunihiko
5 Woodruff, David P.
5 Yang, Chang-Biau
4 Berry, Vincent
4 Farach-Colton, Martin
4 Fernández Anta, Antonio
4 Grabowski, Szymon
4 Hor, Chiou-Yi
4 I, Tomohiro
4 Kopelowitz, Tsvi
4 Na, Joong Chae
4 Nakashima, Yuto
4 Narisawa, Kazuyuki
4 Nelson, Jelani
4 Smid, Michiel H. M.
4 Stølting Brodal, Gerth
4 Tirthapura, Srikanta
4 Tseng, Chiou-Ting
4 Wang, Biing-Feng
3 Adjeroh, Donald A.
3 Ann, Hsing-Yen
3 Bender, Michael A.
3 Blanchet-Sadri, Francine
3 Bose, Prosenjit K.
3 Chan, Timothy Moon-Yew
3 Chen, Kuanyu
3 Gagie, Travis
3 He, Meng
3 Kubica, Marcin
3 Lam, Tak-Wah
3 Levy, Avivit
3 Mäkinen, Veli
3 Maneth, Sebastian
3 Manzini, Giovanni
3 Munro, J. Ian
3 Nakamura, Kengo
3 Nicolas, François
3 Patil, Manish
3 Peng, Yung-Hsing
3 Pontelli, Enrico
3 Puerto Albandoz, Justo
3 Ranjan, Desh
3 Schmidt, Jens M.
3 Shinohara, Ayumi
3 Silveira, Rodrigo I.
3 Sim, Jeong Seop
3 Skala, Matthew
3 Starikovskaya, Tatiana A.
3 Tam, Siu-Lung
3 Tamir, Arie
3 Vitter, Jeffrey Scott
3 Weimann, Oren
3 Zeh, Norbert
3 Zhang, Jingru
2 Bae, Sang Won
2 Barton, Carl
2 Beal, Richard
2 Cafaro, Massimo
2 Caragiannis, Ioannis
2 Charalampopoulos, Panagiotis
2 Chen, Danny Ziyi
2 Colazzo, Dario
2 Cole, Richard John
2 Cording, Patrick Hagge
2 Dal Palù, Alessandro
2 Davoodi, Pooya
2 de Berg, Mark Theodoor
...and 537 more Authors
all top 5

Cited in 59 Serials

64 Theoretical Computer Science
53 Algorithmica
32 Information Processing Letters
22 Journal of Discrete Algorithms
16 Discrete Applied Mathematics
13 Information and Computation
12 Computational Geometry
10 Journal of Computer and System Sciences
8 SIAM Journal on Computing
6 Distributed Computing
6 Algorithms
5 Information Sciences
5 Journal of Combinatorial Optimization
4 Discrete & Computational Geometry
4 International Journal of Foundations of Computer Science
3 Networks
3 Journal of Parallel and Distributed Computing
3 Theory of Computing Systems
3 Data Mining and Knowledge Discovery
3 Journal of Machine Learning Research (JMLR)
3 ACM Journal of Experimental Algorithmics
2 Computers & Mathematics with Applications
2 SIAM Journal on Matrix Analysis and Applications
2 International Journal of Computational Geometry & Applications
2 Journal of Mathematical Imaging and Vision
2 Journal of the ACM
2 Mathematics in Computer Science
1 ACM Computing Surveys
1 Artificial Intelligence
1 Discrete Mathematics
1 International Journal of Systems Science
1 Applied Mathematics and Computation
1 Computing
1 Fuzzy Sets and Systems
1 Journal of Combinatorial Theory. Series A
1 Mathematics of Operations Research
1 Graphs and Combinatorics
1 Journal of Complexity
1 New Generation Computing
1 SIAM Journal on Discrete Mathematics
1 Annals of Operations Research
1 MSCS. Mathematical Structures in Computer Science
1 Geometric and Functional Analysis. GAFA
1 European Journal of Operational Research
1 Information Systems
1 Pattern Recognition
1 Mathematical Programming. Series A. Series B
1 Cybernetics and Systems Analysis
1 Top
1 Constraints
1 Mathematical Problems in Engineering
1 Journal of the European Mathematical Society (JEMS)
1 Journal of Applied Mathematics
1 Sādhanā
1 Computer Languages, Systems & Structures
1 Statistical Analysis and Data Mining
1 Japanese Journal of Mathematics. 3rd Series
1 ACM Transactions on Algorithms
1 Computer Science Review

Citations by Year