Darren Strash

Dr. Darren Strash

orcid

Research Focus & Metrics

Academic Career Length

18Years (2009-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2010
Verified
Book Chapter
Closed access
PDF file
DEDavid Eppstein
David Eppstein
MLMaarten Löffler
Maarten Löffler
DSDarren Strash
Darren Strash

28 November 2013 in ACM Journal of Experimental Algorithmics
Verified
Journal Article
Open access
DEDavid Eppstein
David Eppstein
MLMaarten Löffler
Maarten Löffler
DSDarren Strash
Darren Strash

1 January 2011
Verified
Book Chapter
Closed access
PDF file
DEDavid Eppstein
David Eppstein
DSDarren Strash
Darren Strash

23 May 2017 in Journal of Heuristics
Verified
Journal Article
Closed access
PDF file
SLSebastian Lamm
Sebastian Lamm
PSPeter Sanders
Peter Sanders
CSChristian Schulz
Christian Schulz
DSDarren Strash
Darren Strash
RWRenato F. Werneck
Renato F. Werneck

2 January 2019
Verified
Book Chapter
Closed access
SLSebastian Lamm
Sebastian Lamm
CSChristian Schulz
Christian Schulz
DSDarren Strash
Darren Strash
RWRobert Williger
Robert Williger
HZHuashuo Zhang
Huashuo Zhang
One powerful technique to solve NP-hard optimization problems in practice is branch-and-reduce search—which is branch-and-bound that intermixes branching with reductions to decrease the input size. While this technique is known to be very effective in practice for unweighted problems, very little is known for weighted problems, in part due to a lack of known effective reductions. In this work, we develop a full suite of new reductions for the maximum weight independent set problem and provide extensive experiments to show their effectiveness in practice on real-world graphs of up to millions of vertices and edges. Our experiments indicate that our approach is able to outperform existing state-of-the-art algorithms, solving many instances that were previously infeasible. In particular, we show that branch-and-reduce is able to solve a large number of instances up to two orders of magnitude faster than existing (inexact) local search algorithms—and is able to solve the majority of instances within 15 minutes. For those instances remaining infeasible, we show that combining kernelization with local search produces higher-quality solutions than local search alone.

1 April 2018 in Computers & Operations Research
Verified
Journal Article
Closed access
PSPablo San Segundo
Pablo San Segundo
JAJorge Artieda
Jorge Artieda
DSDarren Strash
Darren Strash