Edith Cohen

I am a research scientist at Google. My research interests include Algorithms, Data Mining, Networks, and more. Also see http://www.cohenwang.com/edith/

Previous Publications

  •  

    All-Distances Sketches

    Edith Cohen

    Encyclopedia of Algorithms (2015)

  •  

    All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis

    Edith Cohen

    IEEE Trans. Knowl. Data Eng., vol. 27 (2015), pp. 2320-2334

  •  

    Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees

    Shiri Chechik, Edith Cohen, Haim Kaplan

    APPROX-RANDOM (2015), pp. 659-679

  •  

    Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees

    Shiri Chechik, Edith Cohen, Haim Kaplan

    CoRR, vol. abs/1503.08528 (2015)

  •  

    Coordinated Sampling

    Edith Cohen

    Encyclopedia of Algorithms (2015)

  •  

    Min-Hash Sketches

    Edith Cohen

    Encyclopedia of Algorithms (2015)

  •  

    Multi-Objective Weighted Sampling

    Edith Cohen

    CoRR, vol. abs/1509.07445 (2015)

  •  

    Reverse Ranking by Graph Structure: Model and Scalable Algorithms

    Eliav Buchnik, Edith Cohen

    CoRR, vol. abs/1506.02386 (2015)

  •  

    Stream Sampling for Frequency Cap Statistics

    Edith Cohen

    CoRR, vol. abs/1502.05955 (2015)

  •  

    Stream Sampling for Frequency Cap Statistics

    Edith Cohen

    KDD (2015), pp. 159-168

  •  

    Algorithms and estimators for summarization of unaggregated data streams

    Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup

    J. Comput. Syst. Sci., vol. 80 (2014), pp. 1214-1244

  •  

    All-distances sketches, revisited: HIP estimators for massive graphs analysis

    Edith Cohen

    PODS (2014), pp. 88-99

  •  

    Author retrospective for search and replication in unstructured peer-to-peer networks

    Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker

    ICS 25th Anniversary (2014), pp. 64-82

  •  

    Computing Classic Closeness Centrality, at Scale

    Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck

    CoRR, vol. abs/1409.0035 (2014)

  •  

    Computing classic closeness centrality, at scale

    Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck

    COSN (2014), pp. 37-50

  •  

    Distance queries from sampled data: accurate and efficient

    Edith Cohen

    KDD (2014), pp. 681-690

  •  

    Estimation for monotone sampling: competitiveness and customization

    Edith Cohen

    PODC (2014), pp. 124-133

  •  

    Probe scheduling for efficient detection of silent failures

    Edith Cohen, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Danny Raz, Yoav Tzur

    Perform. Eval., vol. 79 (2014), pp. 73-89

  •  

    Sketch-based Influence Maximization and Computation: Scaling up with Guarantees

    Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck

    CIKM (2014), pp. 629-638

  •  

    Sketch-based Influence Maximization and Computation: Scaling up with Guarantees

    Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck

    CoRR, vol. abs/1408.6282 (2014)

  •  

    Timed Influence: Computation and Maximization

    Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck

    CoRR, vol. abs/1410.6976 (2014)

  •  

    Variance Competitiveness for Monotone Estimation: Tightening the Bounds

    Edith Cohen

    CoRR, vol. abs/1406.6490 (2014)

  •  

    A Labeling Approach to Incremental Cycle Detection

    Edith Cohen, Amos Fiat, Haim Kaplan, Liam Roditty

    CoRR, vol. abs/1310.8381 (2013)

  •  

    On the Tradeoff between Stability and Fit

    Edith Cohen, Graham Cormode, Nick G. Duffield, Carsten Lund

    CoRR, vol. abs/1302.2137 (2013)

  •  

    Probe Scheduling for Efficient Detection of Silent Failures

    Edith Cohen, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Danny Raz, Yoav Tzur

    CoRR, vol. abs/1302.0792 (2013)

  •  

    Scalable Neighborhood Sketching and Distance Distribution Estimation in Graph Datasets: Revisited, Unified, and Improved

    Edith Cohen

    CoRR, vol. abs/1306.3284 (2013)

  •  

    Scalable similarity estimation in social networks: closeness, node labels, and random edge lengths

    Edith Cohen, Daniel Delling, Fabian Fuchs, Andrew V. Goldberg, Moisés Goldszmidt, Renato F. Werneck

    COSN (2013), pp. 131-142

  •  

    Scheduling Subset Tests: One-Time, Continuous, and How They Relate

    Edith Cohen, Haim Kaplan, Yishay Mansour

    APPROX-RANDOM (2013), pp. 81-95

  •  

    What You Can Do with Coordinated Samples

    Edith Cohen, Haim Kaplan

    APPROX-RANDOM (2013), pp. 452-467

  •  

    A Case for Customizing Estimators: Coordinated Samples

    Edith Cohen, Haim Kaplan

    CoRR, vol. abs/1212.0243 (2012)

  •  

    Don't let the negatives bring you down: sampling from streams of signed updates

    Edith Cohen, Graham Cormode, Nick G. Duffield

    SIGMETRICS (2012), pp. 343-354

  •  

    Envy-Free Makespan Approximation

    Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky

    SIAM J. Comput., vol. 41 (2012), pp. 12-25

  •  

    How to Estimate Change from Samples

    Edith Cohen, Haim Kaplan

    CoRR, vol. abs/1203.4903 (2012)

  •  

    What you can do with Coordinated Samples

    Edith Cohen, Haim Kaplan

    CoRR, vol. abs/1206.5637 (2012)

  •  

    Efficient Stream Sampling for Variance-Optimal Estimation of Subset Sums

    Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup

    SIAM J. Comput., vol. 40 (2011), pp. 1402-1431

  •  

    Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information

    Edith Cohen, Haim Kaplan

    CoRR, vol. abs/1109.1325 (2011)

  •  

    Get the most out of your sample: optimal unbiased estimators using partial information

    Edith Cohen, Haim Kaplan

    PODS (2011), pp. 13-24

  •  

    Structure-Aware Sampling: Flexible and Accurate Summarization

    Edith Cohen, Graham Cormode, Nick G. Duffield

    PVLDB, vol. 4 (2011), pp. 819-830

  •  

    Structure-Aware Sampling: Flexible and Accurate Summarization

    Edith Cohen, Graham Cormode, Nick G. Duffield

    CoRR, vol. abs/1102.5146 (2011)

  •  

    Structure-aware sampling on data streams

    Edith Cohen, Graham Cormode, Nick G. Duffield

    SIGMETRICS (2011), pp. 197-208

  •  

    Truth, Envy, and Truthful Market Clearing Bundle Pricing

    Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky

    WINE (2011), pp. 97-108

  •  

    Envy-free makespan approximation: extended abstract

    Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky

    EC (2010), pp. 159-166

  •  

    Labeling Dynamic XML Trees

    Edith Cohen, Haim Kaplan, Tova Milo

    SIAM J. Comput., vol. 39 (2010), pp. 2048-2074

  •  

    On the Interplay between Incentive Compatibility and Envy Freeness

    Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky

    CoRR, vol. abs/1003.5328 (2010)

  •  

    Truth and Envy in Capacitated Allocation Games

    Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky

    CoRR, vol. abs/1003.5326 (2010)

  •  

    Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets

    Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup

    PVLDB, vol. 2 (2009), pp. 431-442

  •  

    Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments

    Edith Cohen, Haim Kaplan, Subhabrata Sen

    PVLDB, vol. 2 (2009), pp. 646-657

  •  

    Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments

    Edith Cohen, Haim Kaplan, Subhabrata Sen

    CoRR, vol. abs/0906.4560 (2009)

  •  

    Decay Models

    Edith Cohen

    Encyclopedia of Database Systems (2009), pp. 757-761

  •  

    Envy-Free Makespan Approximation

    Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky

    CoRR, vol. abs/0909.1072 (2009)

  •  

    Leveraging Discarded Samples for Tighter Estimation of Multiple-Set Aggregates

    Edith Cohen, Haim Kaplan

    CoRR, vol. abs/0903.0625 (2009)

  •  

    Leveraging discarded samples for tighter estimation of multiple-set aggregates

    Edith Cohen, Haim Kaplan

    SIGMETRICS/Performance (2009), pp. 251-262

  •  

    Stream sampling for variance-optimal estimation of subset sums

    Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup

    SODA (2009), pp. 1255-1264

  •  

    Confident estimation for multistage measurement sampling and aggregation

    Edith Cohen, Nick G. Duffield, Carsten Lund, Mikkel Thorup

    SIGMETRICS (2008), pp. 109-120

  •  

    Estimating Aggregates over Multiple Sets

    Edith Cohen, Haim Kaplan

    ICDM (2008), pp. 761-766

  •  

    Processing top-k queries from samples

    Edith Cohen, Nadav Grossaug, Haim Kaplan

    Computer Networks, vol. 52 (2008), pp. 2605-2622

  •  

    Sketch-Based Estimation of Subpopulation-Weight

    Edith Cohen, Haim Kaplan

    CoRR, vol. abs/0802.3448 (2008)

  •  

    Tighter estimation using bottom k sketches

    Edith Cohen, Haim Kaplan

    PVLDB, vol. 1 (2008), pp. 213-224

  •  

    Variance optimal sampling based estimation of subset sums

    Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup

    CoRR, vol. abs/0803.0473 (2008)

  •  

    Algorithms and estimators for accurate summarization of internet traffic

    Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup

    Internet Measurement Comference (2007), pp. 265-278

  •  

    Associative search in peer to peer networks: Harnessing latent semantics

    Edith Cohen, Amos Fiat, Haim Kaplan

    Computer Networks, vol. 51 (2007), pp. 1861-1881

  •  

    Bottom-k sketches: better and more efficient estimation of aggregates

    Edith Cohen, Haim Kaplan

    SIGMETRICS (2007), pp. 353-354

  •  

    Sketching unaggregated data streams for subpopulation-size queries

    Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup

    PODS (2007), pp. 253-262

  •  

    Spatially-decaying aggregation over a network

    Edith Cohen, Haim Kaplan

    J. Comput. Syst. Sci., vol. 73 (2007), pp. 265-288

  •  

    Summarizing data using bottom-k sketches

    Edith Cohen, Haim Kaplan

    PODC (2007), pp. 225-234

  •  

    A short walk in the Blogistan

    Edith Cohen, Balachander Krishnamurthy

    Computer Networks, vol. 50 (2006), pp. 615-630

  •  

    Maintaining time-decaying stream aggregates

    Edith Cohen, Martin J. Strauss

    J. Algorithms, vol. 59 (2006), pp. 19-36

  •  

    Making routing robust to changing traffic demands: algorithms and evaluation

    David Applegate, Edith Cohen

    IEEE/ACM Trans. Netw., vol. 16 (2006), pp. 1193-1206

  •  

    Processing top k queries from samples

    Edith Cohen, Nadav Grossaug, Haim Kaplan

    CoNEXT (2006), pp. 7

  •  

    Packet classification in large ISPs: design and evaluation of decision tree classifiers

    Edith Cohen, Carsten Lund

    SIGMETRICS (2005), pp. 73-84

  •  

    Performance aspects of distributed caches using TTL-based consistency

    Edith Cohen, Eran Halperin, Haim Kaplan

    Theor. Comput. Sci., vol. 331 (2005), pp. 73-96

  •  

    Balanced-Replication Algorithms for Distribution Trees

    Edith Cohen, Haim Kaplan

    SIAM J. Comput., vol. 34 (2004), pp. 227-247

  •  

    Coping with network failures: routing strategies for optimal demand oblivious restoration

    David Applegate, Lee Breslau, Edith Cohen

    SIGMETRICS (2004), pp. 270-281

  •  

    Efficient estimation algorithms for neighborhood variance and other moments

    Edith Cohen, Haim Kaplan

    SODA (2004), pp. 157-166

  •  

    Guest Editors' foreword

    Edith Cohen, Venkatesan Guruswami

    J. Comput. Syst. Sci., vol. 68 (2004), pp. 701

  •  

    Optimal oblivious routing in polynomial time

    Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke

    J. Comput. Syst. Sci., vol. 69 (2004), pp. 383-394

  •  

    Spatially-decaying aggregation over a network: model and algorithms

    Edith Cohen, Haim Kaplan

    SIGMOD Conference (2004), pp. 707-718

  •  

    A case for associative peer to peer overlays

    Edith Cohen, Amos Fiat, Haim Kaplan

    Computer Communication Review, vol. 33 (2003), pp. 95-100

  •  

    Associative Search in Peer to Peer Networks: Harnessing Latent Semantics

    Edith Cohen, Amos Fiat, Haim Kaplan

    INFOCOM (2003)

  •  

    Connection caching: model and algorithms

    Edith Cohen, Haim Kaplan, Uri Zwick

    J. Comput. Syst. Sci., vol. 67 (2003), pp. 92-126

  •  

    Efficient sequences of trials

    Edith Cohen, Amos Fiat, Haim Kaplan

    SODA (2003), pp. 737-746

  •  

    Maintaining time-decaying stream aggregates

    Edith Cohen, Martin Strauss

    PODS (2003), pp. 223-233

  •  

    Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs

    David Applegate, Edith Cohen

    SIGCOMM (2003), pp. 313-324

  •  

    Optimal oblivious routing in polynomial time

    Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke

    STOC (2003), pp. 383-388

  •  

    Predicting and bypassing end-to-end Internet service degradations

    Anat Bremler-Barr, Edith Cohen, Haim Kaplan, Yishay Mansour

    IEEE Journal on Selected Areas in Communications, vol. 21 (2003), pp. 961-978

  •  

    Proactive caching of DNS records: addressing a performance bottleneck

    Edith Cohen, Haim Kaplan

    Computer Networks, vol. 41 (2003), pp. 707-726

  •  

    Reachability and Distance Queries via 2-Hop Labels

    Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick

    SIAM J. Comput., vol. 32 (2003), pp. 1338-1355

  •  

    Balanced-Replication Algorithms for Distribution Trees

    Edith Cohen, Haim Kaplan

    ESA (2002), pp. 297-309

  •  

    Caching Documents with Variable Sizes and Fetching Costs: An LP-Based Approach

    Edith Cohen, Haim Kaplan

    Algorithmica, vol. 32 (2002), pp. 459-466

  •  

    Competitive Analysis of the LRFU Paging Algorithm

    Edith Cohen, Haim Kaplan, Uri Zwick

    Algorithmica, vol. 33 (2002), pp. 511-516

  •  

    Exploiting Regularities in Web Traffic Patterns for Cache Replacement

    Edith Cohen, Haim Kaplan

    Algorithmica, vol. 33 (2002), pp. 300-334

  •  

    Labeling Dynamic XML Trees

    Edith Cohen, Haim Kaplan, Tova Milo

    PODS (2002), pp. 271-281

  •  

    Predicting and bypassing end-to-end internet service degradations

    Anat Bremler-Barr, Edith Cohen, Haim Kaplan, Yishay Mansour

    Internet Measurement Workshop (2002), pp. 307-320

  •  

    Prefetching the means for document transfer: a new approach for reducing Web latency

    Edith Cohen, Haim Kaplan

    Computer Networks, vol. 39 (2002), pp. 437-455

  •  

    Reachability and distance queries via 2-hop labels

    Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick

    SODA (2002), pp. 937-946

  •  

    Refreshment policies for Web content caches

    Edith Cohen, Haim Kaplan

    Computer Networks, vol. 38 (2002), pp. 795-808

  •  

    Replication strategies in unstructured peer-to-peer networks

    Edith Cohen, Scott Shenker

    SIGCOMM (2002), pp. 177-190

  •  

    Restoration by path concatenation: fast recovery of MPLS paths

    Yehuda Afek, Anat Bremler-Barr, Haim Kaplan, Edith Cohen, Michael Merritt

    Distributed Computing, vol. 15 (2002), pp. 273-283

  •   

    Search and replication in unstructured peer-to-peer networks

    Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker

    ICS (2002), pp. 84-95

  •   

    Search and replication in unstructured peer-to-peer networks

    Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker

    SIGMETRICS (2002), pp. 258-259

  •  

    Aging through cascaded caches: performance issues in the distribution of web content

    Edith Cohen, Haim Kaplan

    SIGCOMM (2001), pp. 41-53

  •  

    All-Pairs Small-Stretch Paths

    Edith Cohen, Uri Zwick

    J. Algorithms, vol. 38 (2001), pp. 335-353

  •  

    Competitive Analysis of the LRFU Paging Algorithm

    Edith Cohen, Haim Kaplan, Uri Zwick

    WADS (2001), pp. 148-154

  •   

    Finding Interesting Associations without Support Pruning

    Edith Cohen, Mayur Datar, Shinji Fujiwara, Aristides Gionis, Piotr Indyk, Rajeev Motwani, Jeffrey D. Ullman, Cheng Yang

    IEEE Trans. Knowl. Data Eng., vol. 13 (2001), pp. 64-78

  •  

    Performance Aspects of Distributed Caches Using TTL-Based Consistency

    Edith Cohen, Eran Halperin, Haim Kaplan

    ICALP (2001), pp. 744-756

  •  

    Proactive Caching of DNS Records: Addressing a Performance Bottleneck

    Edith Cohen, Haim Kaplan

    SAINT (2001), pp. 85-94

  •  

    Refreshment Policies for Web Content Caches

    Edith Cohen, Haim Kaplan

    INFOCOM (2001), pp. 1398-1406

  •  

    Restoration by path concatenation: fast recovery of MPLS paths

    Anat Bremler-Barr, Yehuda Afek, Haim Kaplan, Edith Cohen, Michael Merritt

    PODC (2001), pp. 43-52

  •  

    Restoration path concatenation: fast recovery of MPLS paths

    Anat Bremler-Barr, Yehuda Afek, Haim Kaplan, Edith Cohen, Michael Merritt

    SIGMETRICS/Performance (2001), pp. 316-317

  •  

    The Age Penalty and Its Effect on Cache Performance

    Edith Cohen, Haim Kaplan

    USITS (2001), pp. 73-84

  •  

    Connection caching under vaious models of communication

    Edith Cohen, Haim Kaplan, Uri Zwick

    SPAA (2000), pp. 54-63

  •   

    Finding Interesting Associations without Support Pruning

    Edith Cohen, Mayur Datar, Shinji Fujiwara, Aristides Gionis, Piotr Indyk, Rajeev Motwani, Jeffrey D. Ullman, Cheng Yang

    ICDE (2000), pp. 489-499

  •  

    Polylog-time and near-linear work approximation scheme for undirected shortest paths

    Edith Cohen

    J. ACM, vol. 47 (2000), pp. 132-166

  •  

    Prefetching the Means for Document Transfer: A New Approach for Reducing Web Latency

    Edith Cohen, Haim Kaplan

    INFOCOM (2000), pp. 854-863

  •  

    Approximating Matrix Multiplication for Pattern Recognition Tasks

    Edith Cohen, David D. Lewis

    J. Algorithms, vol. 30 (1999), pp. 211-252

  •  

    Connection Caching

    Edith Cohen, Haim Kaplan, Uri Zwick

    STOC (1999), pp. 612-621

  •  

    Efficient Algorithms for Predicting Requests to Web Servers

    Edith Cohen, Balachander Krishnamurthy, Jennifer Rexford

    INFOCOM (1999), pp. 284-293

  •  

    Exploiting Regularities in Web Traffic Patterns for Cache Replacement

    Edith Cohen, Haim Kaplan

    STOC (1999), pp. 109-118

  •  

    LP-based Analysis of Greedy-dual-size

    Edith Cohen, Haim Kaplan

    SODA (1999), pp. 879-880

  •   

    Managing TCP Connections Under Persistent HTTP

    Edith Cohen, Haim Kaplan, Jeffrey D. Oldham

    Computer Networks, vol. 31 (1999), pp. 1709-1723

  •  

    Evaluating Server-Assisted Cache Replacement in the Web

    Edith Cohen, Balachander Krishnamurthy, Jennifer Rexford

    ESA (1998), pp. 307-319

  •  

    Fast Algorithms for Constructing t-Spanners and Paths with Stretch t

    Edith Cohen

    SIAM J. Comput., vol. 28 (1998), pp. 210-236

  •  

    Improving End-to-End Performance of the Web Using Server Volumes and Proxy Filters

    Edith Cohen, Balachander Krishnamurthy, Jennifer Rexford

    SIGCOMM (1998), pp. 241-253

  •  

    Structure Prediction and Computation of Sparse Matrix Products

    Edith Cohen

    J. Comb. Optim., vol. 2 (1998), pp. 307-332

  •  

    All-Pairs Small-Stretch Paths

    Edith Cohen, Uri Zwick

    SODA (1997), pp. 93-102

  •  

    Approximating Matrix Multiplication for Pattern Recognition Tasks

    Edith Cohen, David D. Lewis

    SODA (1997), pp. 682-691

  •  

    Learning Noisy Perceptrons by a Perceptron in Polynomial Time

    Edith Cohen

    FOCS (1997), pp. 514-523

  •  

    Size-Estimation Framework with Applications to Transitive Closure and Reachability

    Edith Cohen

    J. Comput. Syst. Sci., vol. 55 (1997), pp. 441-453

  •  

    Using Selective Path-Doubling for Parallel Shortest-Path Computations

    Edith Cohen

    J. Algorithms, vol. 22 (1997), pp. 30-56

  •  

    Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition

    Edith Cohen

    J. Algorithms, vol. 21 (1996), pp. 331-357

  •  

    On Optimizing Multiplications of Sparse Matrices

    Edith Cohen

    IPCO (1996), pp. 219-233

  •  

    Approximate Max-Flow on Small Depth Networks

    Edith Cohen

    SIAM J. Comput., vol. 24 (1995), pp. 579-597

  •  

    Improvise: Interactive Multimedia Process Visualization Environment

    Naser S. Barghouti, Eleftherios Koutsofios, Edith Cohen

    ESEC (1995), pp. 28-43

  •  

    Algorithms and Complexity Analysis for Some Flow Problems

    Edith Cohen, Nimrod Megiddo

    Algorithmica, vol. 11 (1994), pp. 320-340

  •  

    Estimating the Size of the Transitive Closure in Linear Time

    Edith Cohen

    FOCS (1994), pp. 190-200

  •  

    Improved Algorithms for Linear Inequalities With Two Variables per Inequality

    Edith Cohen, Nimrod Megiddo

    SIAM J. Comput., vol. 23 (1994), pp. 1313-1347

  •  

    New algorithms for generalized network flows

    Edith Cohen, Nimrod Megiddo

    Math. Program., vol. 64 (1994), pp. 325-336

  •  

    Polylog-time and near-linear work approximation scheme for undirected shortest paths

    Edith Cohen

    STOC (1994), pp. 16-26

  •  

    Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition

    Edith Cohen

    SPAA (1993), pp. 57-67

  •  

    Fast algorithms for constructing t-spanners and paths with stretch t

    Edith Cohen

    FOCS (1993), pp. 648-658

  •  

    Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Periodic Graphs

    Edith Cohen, Nimrod Megiddo

    J. ACM, vol. 40 (1993), pp. 791-830

  •  

    Using Selective Path-Doubling for Parallel Shortest-Path Computations

    Edith Cohen

    ISTCS (1993), pp. 78-87

  •  

    Approximate Max Flow on Small Depth Networks

    Edith Cohen

    FOCS (1992), pp. 648-658

  •  

    New Algorithms for Generalized Network Flows

    Edith Cohen, Nimrod Megiddo

    ISTCS (1992), pp. 103-114

  •  

    Algorithms and Complexity Analysis for Some Flow Problems

    Edith Cohen, Nimrod Megiddo

    SODA (1991), pp. 120-130

  •  

    Improved Algorithms for Linear Inequalities with Two Variables per Inequality (Extended Abstract)

    Edith Cohen, Nimrod Megiddo

    STOC (1991), pp. 145-155

  •  

    NP-Completeness of graph decomposition problems

    Edith Cohen, Michael Tarsi

    J. Complexity, vol. 7 (1991), pp. 200-212

  •  

    Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Dynamic Graphs (Preliminary Version)

    Edith Cohen, Nimrod Megiddo

    STOC (1989), pp. 523-534