9 Result(s)
within
English
Computation by Abstract Devices
Theory of Computation
David Fernández-Baca
Chapter
Conference Paper
-
Chapter and Conference Paper
Space-sweep algorithms for parametric optimization
-
Chapter and Conference Paper
On matroids and hierarchical graphs
-
Chapter and Conference Paper
Solving the Lagrangian dual when the number of constraints is fixed
Good bounds on the optimum value of hard optimization problems can often be efficiently obtained by “pricing out” certain “bad” constraints and incorporating them into the objective function. The resulting pro...
-
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
Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
We give a linear-time algorithm for the minimum-ratio spanning tree problem on planar graphs. The algorithm is based on a new planar minimum spanning tree algorithm. The approach extends to other parametric mi...
-
Chapter and Conference Paper
On the approximability of the Steiner tree problem in phylogeny
Three results on the Steiner tree problem are presented: (i) Computing optimum k-restricted Steiner tree is APX-complete for k≥4, (ii) the minimum-cost k-restricted Steiner tree problem in phylogeny is APX-comple...
-
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
Multi-parameter Minimum Spanning Trees
A framework for solving certain multidimensional parametric search problems in randomized linear time is presented, along with its application to optimization on matroids, including parametric minimum spanning...
-
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...
