10 Result(s)
within
English
Data Structures
David Fernández-Baca
Chapter
Conference Paper
-
Chapter and Conference Paper
Augmentation problems on hierarchically defined graphs
-
Chapter and Conference Paper
Space-sweep algorithms for parametric optimization
-
Chapter and Conference Paper
On matroids and hierarchical graphs
-
Chapter and Conference Paper
Optimal parametric search on graphs of bounded tree-width
We give linear-time algorithms for a class of parametric search problems on weighted graphs of bounded tree-width. We also discuss the implications of our results to approximate parametric search on planar gra...
-
Chapter and Conference Paper
A polynomial-time algorithm for near-perfect phylogeny
We define a parameterized version of the Steiner tree problem in phylogeny where the parameter measures the amount by which a phylogeny differs from “perfection.” This problem is shown to be solvable in polyno...
-
Chapter and Conference Paper
Using sparsification for parametric minimum spanning tree problems
Two applications of sparsification to parametric computing are given. The first is a fast algorithm for enumerating all distinct minimum spanning trees in a graph whose edge weights vary linearly with a parame...
-
Chapter and Conference Paper
Parametric Analysis for Ungapped Markov Models of Evolution
We present efficient sensitivity-analysis algorithms for two problems involving Markov models of sequence evolution: ancestral reconstruction in evolutionary trees and local ungapped alignment under log-odds s...
-
Chapter and Conference Paper
Comparing and Aggregating Partially Resolved Trees
We define, analyze, and give efficient algorithms for two kinds of distance measures for rooted and unrooted phylogenies. For rooted trees, our measures are based on the topologies the input trees induce on tripl...
-
Chapter and Conference Paper
Constructing Large Conservative Supertrees
Generalizations of the strict and loose consensus methods to the supertree setting, recently introduced by McMorris and Wilkinson, are studied. The supertrees these methods produce are conservative in the sens...
-
Chapter and Conference Paper
Fixed-Parameter Algorithms for Finding Agreement Supertrees
We study the agreement supertree approach for combining rooted phylogenetic trees when the input trees do not fully agree on the relative positions of the taxa. Two approaches to dealing with such conflicting ...
