Springer Science and Business Media LLC
Công bố khoa học tiêu biểu
* Dữ liệu chỉ mang tính chất tham khảo
Sắp xếp:
A Divide-and-Conquer Approach to the Minimum k -Way Cut Problem
Springer Science and Business Media LLC - Tập 32 - Trang 262-276 - 2002
This paper presents algorithms for computing a minimum 3 -way cut and a minimum 4 -way cut of an undirected weighted graph G . Let G=(V, E) be an undirected graph with n vertices, m edges, and positive edge weights. Goldschmidt and Hochbaum presented an algorithm for the minimum k -way cut problem with fixed k , that requires O(n
4
) and O(n
......
Approximation Algorithms for Bounded Degree Phylogenetic Roots
Springer Science and Business Media LLC - Tập 51 - Trang 1-23 - 2007
The Degree-
Δ
Closest Phylogenetic
k
th Root Problem (ΔCPR
k
) is the problem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) the degree of each internal node in T is at least 3 and at most Δ, (2) the external nodes (i.e. leaves) of T are ex......
Quantum Algorithms for Weighing Matrices and Quadratic Residues
Springer Science and Business Media LLC - Tập 34 - Trang 413-428 - 2002
Abstract. In this article we investigate how we can employ the structure of combinatorial objects like Hadamard matrices and weighing matrices to devise new quantum algorithms. We show how the properties of a weighing matrix can be used to construct a problem for which the quantum query complexity is significantly lower than the classical one. It is pointed out that this scheme captures both Bern......
Security of Quantum Key Distribution against All Collective Attacks
Springer Science and Business Media LLC - Tập 34 - Trang 372-388 - 2002
Abstract. Security of quantum key distribution against sophisticated attacks is among the most important issues in quantum information theory. In this work we prove security against a very important class of attacks called collective attacks (under a compatible noise model) which use quantum memories and gates, and which are directed against the final key. This work was crucial for a full proof ......
Optimal Point Movement for Covering Circular Regions
Springer Science and Business Media LLC - - 2013
Given n points in a circular region C in the plane, we study the problems of moving the n points to the boundary of G to form a regular n-gon such that the maximum (min-max) or the sum (min-sum) of the Euclidean distances traveled by the points is minimized. These problems have applications, e.g., in mobile sensor barrier coverage of wireless sensor networks. The min-max problem further has two ve......
Multikey Quickselect
Springer Science and Business Media LLC - Tập 69 Số 4 - Trang 958-973 - 2014
We present multikey quickselect: an efficient, in-place, easy-to-implement algorithm for the selection problem for strings. We analyze its expected cost under a uniform model, measured as the number of character comparisons and pointer swaps, depending on the alphabet cardinality. From the analysis, we derive a binary variant of the algorithm, which is more efficient when the range of values for t......
The implementation of linear programming algorithms based on homotopies
Springer Science and Business Media LLC - Tập 15 - Trang 332-350 - 1996
A fundamental homotopy-based linear programming algorithm, which utilizes Euler-predictor and Newton-corrector steps with restarts, is formulated and investigated numerically on problems representative of linear programs that arise in practice. A rich array of refinements of this basic algorithm are possible within the homotopy framework. Such refinements are needed in any practical implementation......
Improved Pseudo-polynomial Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games
Springer Science and Business Media LLC - Tập 77 - Trang 995-1021 - 2016
In this work we offer an
$$O(|V|^2 |E|\, W)$$
pseudo-polynomial time deterministic algorithm for solving the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games. This improves by a factor
......
Optimal parallel algorithms for multiple updates of minimum spanning trees
Springer Science and Business Media LLC - Tập 9 - Trang 357-381 - 1993
Parallel updates of minimum spanning trees (MSTs) have been studied in the past. These updates allowed a single change in the underlying graph, such as a change in the cost of an edge or an insertion of a new vertex. Multiple update problems for MSTs are concerned with handling more than one such change. In the sequential case multiple update problems may be solved using repeated applications of a......
Efficient Algorithms for Computing a Complete Visibility Region in Three-Dimensional Space
Springer Science and Business Media LLC - Tập 20 Số 2 - Trang 201-225 - 1998
Tổng số: 2,408
- 1
- 2
- 3
- 4
- 5
- 6
- 10