Dan Gusfield

Affiliations:
  • University of California, Davis, USA


According to our database1, Dan Gusfield authored at least 117 papers between 1983 and 2021.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2017, "For contributions to combinatorial optimization and to algorithmic computational biology".

IEEE Fellow

IEEE Fellow 2015, "For contributions to combinatorial optimization and computational biology".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2021
Matrix Chain Multiplication and Polygon Triangulation Revisited and Generalized.
CoRR, 2021

2020
Comparing Integer Linear Programming to SAT-Solving for Hard Problems in Computational and Systems Biology.
Proceedings of the Algorithms for Computational Biology, 2020

2019
Integer Linear Programming in Computational and Systems Biology: Tutorial.
Proceedings of the 10th ACM International Conference on Bioinformatics, 2019

2017
A Resolution of the Static Formulation Question for the Problem of Computing the History Bound.
IEEE ACM Trans. Comput. Biol. Bioinform., 2017

2016
An improved Four-Russians method and sparsified Four-Russians algorithm for RNA folding.
Algorithms Mol. Biol., 2016

2015
Minimum Average Distance Clique Trees.
SIAM J. Discret. Math., 2015

Association Mapping for Compound Heterozygous Traits Using Phenotypic Distance and Integer Programming.
Proceedings of the Algorithms in Bioinformatics - 15th International Workshop, 2015

A Sparsified Four-Russian Algorithm for RNA Folding.
Proceedings of the Algorithms in Bioinformatics - 15th International Workshop, 2015

Construction, enumeration, and optimization of perfect phylogenies on multi-state data.
Proceedings of the 5th IEEE International Conference on Computational Advances in Bio and Medical Sciences, 2015

Persistent phylogeny: a galled-tree and integer linear programming approach.
Proceedings of the 6th ACM Conference on Bioinformatics, 2015

2014
Gödel for Goldilocks: A Rigorous, Streamlined Proof of Gödel's First Incompleteness Theorem, Requiring Minimal Background.
CoRR, 2014

Faster algorithms for RNA-folding using the Four-Russians method.
Algorithms Mol. Biol., 2014

2013
Triangulation heuristics for maximum character compatibility.
Proceedings of the IEEE 3rd International Conference on Computational Advances in Bio and Medical Sciences, 2013

2012
Constructing perfect phylogenies and proper triangulations for three-state characters.
Algorithms Mol. Biol., 2012

Reducing Problems in Unrooted Tree Compatibility to Restricted Triangulations of Intersection Graphs.
Proceedings of the Algorithms in Bioinformatics - 12th International Workshop, 2012

Speedup of RNA Pseudoknotted Secondary Structure Recurrence Computation with the Four-Russians Method.
Proceedings of the Combinatorial Optimization and Applications, 2012

2011
Extensions and Improvements to the Chordal Graph Approach to the Multistate Perfect Phylogeny Problem.
IEEE ACM Trans. Comput. Biol. Bioinform., 2011

Generalizing the Splits Equivalence Theorem and Four Gamete Condition: Perfect Phylogeny on Three-State Characters.
SIAM J. Discret. Math., 2011

2010
Untangling Tanglegrams: Comparing Trees by Their Drawings.
IEEE ACM Trans. Comput. Biol. Bioinform., 2010

The Multi-State Perfect Phylogeny Problem with Missing and Removable Data: Solutions via Integer-Programming and Chordal Graph Theory.
J. Comput. Biol., 2010

A simple, practical and complete O-time Algorithm for RNA folding using the Four-Russians Speedup.
Algorithms Mol. Biol., 2010

Reducing Multi-state to Binary Perfect Phylogeny with Applications to Missing, Removable, Inserted, and Deleted Data.
Proceedings of the Algorithms in Bioinformatics, 10th International Workshop, 2010

A Worst-Case and Practical Speedup for the RNA Co-folding Problem Using the <i>Four-Russians</i> Idea.
Proceedings of the Algorithms in Bioinformatics, 10th International Workshop, 2010

Extensions and Improvements to the Chordal Graph Approach to the Multi-state Perfect Phylogeny Problem.
Proceedings of the Bioinformatics Research and Applications, 6th International Symposium, 2010

2009
Outgoing EIC Editorial for this Special Section of TCBB with the Theme of Phylogenetics.
IEEE ACM Trans. Comput. Biol. Bioinform., 2009

Final, Five-Year End, Editorial.
IEEE ACM Trans. Comput. Biol. Bioinform., 2009

The Three-state Perfect Phylogeny Problem Reduces to 2-SAT.
Commun. Inf. Syst., 2009

Editorial.
Bioinform., 2009

Generalizing the Four Gamete Condition and Splits Equivalence Theorem: Perfect Phylogeny on Three State Characters.
Proceedings of the Algorithms in Bioinformatics, 9th International Workshop, 2009

A Simple, Practical and Complete <i>O</i>(\frac<i>n</i><sup>3</sup> log<i>n</i>)O(\frac{n^3}{ \log n})-Time Algorithm for RNA Folding Using the <i>Four-Russians</i> Speedup.
Proceedings of the Algorithms in Bioinformatics, 9th International Workshop, 2009

2008
EIC Editorial.
IEEE ACM Trans. Comput. Biol. Bioinform., 2008

A new recombination lower bound and the minimum perfect phylogenetic forest problem.
J. Comb. Optim., 2008

ReCombinatorics: Combinatorial Algorithms for Studying the History of Recombination in Populations.
Proceedings of the Combinatorial Pattern Matching, 19th Annual Symposium, 2008

2007
Associate Editor Appreciation and Welcome.
IEEE ACM Trans. Comput. Biol. Bioinform., 2007

Algorithms to Distinguish the Role of Gene-Conversion from Single-Crossover Recombination in the Derivation of SNP Sequences in Populations.
J. Comput. Biol., 2007

A Decomposition Theory for Phylogenetic Networks and Incompatible Characters.
J. Comput. Biol., 2007

Efficient Computation of Minimum Recombination with genotypes (not Haplotypes).
J. Bioinform. Comput. Biol., 2007

An efficiently computed lower bound on the number of recombinations in phylogenetic networks: Theory and empirical study.
Discret. Appl. Math., 2007

Improved Algorithms for Inferring the Minimum Mosaic of a Set of Recombinants.
Proceedings of the Combinatorial Pattern Matching, 18th Annual Symposium, 2007

Integer Programming Formulations and Computations Solving Phylogenetic and Population Genetic Problems with Missing or Genotypic Data.
Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006
State of the Journal.
IEEE ACM Trans. Comput. Biol. Bioinform., 2006

A Linear-Time Algorithm for the Perfect Phylogeny Haplotyping (PPH) Problem.
J. Comput. Biol., 2006

Efficient and Practical Algorithms for Deducing the History of Recombination in Populations.
Proceedings of the Computational Science, 2006

2005
Editorial-State of the Transaction.
IEEE ACM Trans. Comput. Biol. Bioinform., 2005

Optimal, efficient reconstruction of root-unknown phylogenetic networks with constrained and structured recombination.
J. Comput. Syst. Sci., 2005

Preface: Special RECOMB 2004 Issue.
J. Comput. Biol., 2005

Algorithms for Imperfect Phylogeny Haplotyping (IPPH) with a Single Homoplasy or Recombination Event.
Proceedings of the Algorithms in Bioinformatics, 5th International Workshop, 2005

A Fundamental Decomposition Theory for Phylogenetic Networks and Incompatible Characters.
Proceedings of the Research in Computational Molecular Biology, 2005

Efficient computation of close lower and upper bounds on the minimum number of recombinations in biological sequence evolution.
Proceedings of the Proceedings Thirteenth International Conference on Intelligent Systems for Molecular Biology 2005, 2005

2004
Introduction of New Associate Editors.
IEEE ACM Trans. Comput. Biol. Bioinform., 2004

Linear time algorithms for finding and representing all the tandem repeats in a string.
J. Comput. Syst. Sci., 2004

A Note on Efficient Computation of Haplotypes via Perfect Phylogeny.
J. Comput. Biol., 2004

Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination.
J. Bioinform. Comput. Biol., 2004

The Fine Structure of Galls in Phylogenetic Networks.
INFORMS J. Comput., 2004

Invited Talk: Phylogenetic Networks with Constrained and Unconstrained Recombination.
Proceedings of the German Conference on Bioinformatics (GCB 2004), Bielefeld, 2004

2003
Neuroanatomical term generation and comparison between two terminologies.
Neuroinformatics, 2003

On the Complexity of Fundamental Computational Problems in Pedigree Analysis.
J. Comput. Biol., 2003

Haplotyping as Perfect Phylogeny: A Direct Approach.
J. Comput. Biol., 2003

Perfect phylogeny haplotyper: haplotype inferral using a tree model.
Bioinform., 2003

An Overview of Haplotyping via Perfect Phylogeny: Theory, Algorithms and Programs.
Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2003), 2003

Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination.
Proceedings of the 2nd IEEE Computer Society Bioinformatics Conference, 2003

Haplotype Inference by Pure Parsimony.
Proceedings of the Combinatorial Pattern Matching, 14th Annual Symposium, 2003

Empirical Exploration of Perfect Phylogeny Haplotyping and Haplotypers.
Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003

2002
Simple and flexible detection of contiguous repeats using a suffix tree.
Theor. Comput. Sci., 2002

Partition-distance: A problem and class of perfect graphs arising in clustering.
Inf. Process. Lett., 2002

The Structure and Complexity of Sports Elimination Numbers.
Algorithmica, 2002

String barcoding: uncovering optimal virus signatures.
Proceedings of the Sixth Annual International Conference on Computational Biology, 2002

An Overview of Combinatorial Methods for Haplotype Inference.
Proceedings of the Computational Methods for SNPs and Haplotype Inference, 2002

Haplotyping as perfect phylogeny: conceptual framework and efficient solutions.
Proceedings of the Sixth Annual International Conference on Computational Biology, 2002

Suffix Trees (and Relatives) Come of Age in Bioinformatics.
Proceedings of the 1st IEEE Computer Society Bioinformatics Conference, 2002

2001
Inference of Haplotypes from Samples of Diploid Populations: Complexity and Algorithms.
J. Comput. Biol., 2001

2000
A More Efficient Approximation Scheme for Tree Alignment.
SIAM J. Comput., 2000

A Practical Algorithm for Optimal Inference of Haplotypes from Diploid Populations.
Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, 2000

1999
Guest Editors' Foreword.
Algorithmica, 1999

Tresholds for Sports Elimination Numbers Algorithms and Complexity.
Proceedings of the Algorithms and Data Structures, 6th International Workshop, 1999

1998
Constructing Additive Trees When the Error Is Small.
J. Comput. Biol., 1998

Reconstructing a History of Recombinations From a Set of Sequences.
Discret. Appl. Math., 1998

Graph Traversals, Genes and Matroids: An Efficient Case of the Travelling Salesman Problem.
Discret. Appl. Math., 1998

New uses for uniform lifted alignments.
Proceedings of the Mathematical Support for Molecular Biology, 1998

Simple and Flexible Detection of Contiguous Repeats Using a Suffix Tree (Preliminary Version).
Proceedings of the Combinatorial Pattern Matching, 9th Annual Symposium, 1998

1997
Algorithms on Stings, Trees, and Sequences: Computer Science and Computational Biology.
SIGACT News, 1997

A Fast Algorithm for Optimally Increasing the Edge Connectivity.
SIAM J. Comput., 1997

Improved Approximation Algorithms for Tree Alignment.
J. Algorithms, 1997

A more efficient approximation scheme for tree alignment.
Proceedings of the First Annual International Conference on Research in Computational Molecular Biology, 1997

Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology
Cambridge University Press, ISBN: 9780511574931, 1997

1994
Faster Implementation of a Shortest Superstring Approximation.
Inf. Process. Lett., 1994

A Faster Parametric Minimum-Cut Algorithm.
Algorithmica, 1994

Parametric Optimization of Sequence Alignment.
Algorithmica, 1994

1993
Efficient Detection and Protection of Information in Cross Tabulated Tables I: Linear Invariant Test.
SIAM J. Discret. Math., 1993

Extracting Maximal Information About Sets of Minimum Cuts.
Algorithmica, 1993

1992
An Efficient Algorithm for the All Pairs Suffix-Prefix Problem.
Inf. Process. Lett., 1992

A Bounded Approximation for the Minimum Cost 2-Sat Problem.
Algorithmica, 1992

A Fast Algorithm for the Generalized Parametric Minimum Cut Problem and Applications.
Algorithmica, 1992

1991
Потоковые Алгоритмы (Flow Algorithms) (G. M. Adel'son-Vel'ski, E. A. Dinits, and A. V. Karzanov).
SIAM Rev., 1991

Computing the Strength of a Graph.
SIAM J. Comput., 1991

Efficient algorithms for generalized cut-trees.
Networks, 1991

Efficient algorithms for inferring evolutionary trees.
Networks, 1991

1990
Very Simple Methods for All Pairs Network Flow Analysis.
SIAM J. Comput., 1990

A Little Knowledge Goes a Long Way: Faster Detection of Compromised Data in 2-D Tables.
Proceedings of the 1990 IEEE Symposium on Security and Privacy, 1990

1989
A Fast Parallel Quicksort Algorithm.
Inf. Process. Lett., 1989

Parametric Stable Marriage and Minimum Cuts.
Inf. Process. Lett., 1989

The Stable marriage problem - structure and algorithms.
Foundations of computing series, MIT Press, ISBN: 978-0-262-07118-5, 1989

1988
The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments.
SIAM J. Comput., 1988

A Graph Theoretic Approach to Statistical Data Security.
SIAM J. Comput., 1988

1987
Fast Algorithms for Bipartite Network Flow.
SIAM J. Comput., 1987

Optimal Mixed Graph Augmentation.
SIAM J. Comput., 1987

Three Fast Algorithms for Four Problems in Stable Marriage.
SIAM J. Comput., 1987

Every finite distributive lattice is a set of stable matchings for a small stable marriage instance.
J. Comb. Theory, Ser. A, 1987

An efficient algorithm for the "optimal" stable marriage.
J. ACM, 1987

1986
Equivalent Approximation Algorithms for Node Cover.
Inf. Process. Lett., 1986

1985
Data structures and algorithms, by A. Aho, J. Hopcroft, and J. Ullman, Addison-Wesley, Reading, Mass., 1983, 427 pp. Price: $28.85.
Networks, 1985

1984
Bounds for Naive Multiple Machine Scheduling with Release Times and Deadlines.
J. Algorithms, 1984

Matroid optimization with the interleaving of two ordered sets.
Discret. Appl. Math., 1984

1983
Parametric Combinatorial Computing and a Problem of Program Module Distribution
J. ACM, July, 1983

Simple Construction for Multi-Terminal Network Flow Synthesis.
SIAM J. Comput., 1983

A note on Arc tolerances in sparse shortest-path and network flow problems.
Networks, 1983

Connectivity and Edge-Disjoint Spanning Trees.
Inf. Process. Lett., 1983


  Loading...