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
Kamidoi, Wakabayashi, Yoshida
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 6 ) maximum flow computations, respectively, to compute ... hiện toàn bộ
Approximation Algorithms for Bounded Degree Phylogenetic Roots
Springer Science and Business Media LLC - Tập 51 - Trang 1-23 - 2007
Zhi-Zhong Chen
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 exactly the elements of V, and (3) the number of disagreements, i.e., |E ⊕{{u,v} : u,v are leaves of T and d T (u,v)≤k}|, is minimize... hiện toàn bộ
Certifying Fully Dynamic Algorithms for Recognition and Hamiltonicity of Threshold and Chain Graphs
Springer Science and Business Media LLC - Tập 85 Số 8 - Trang 2454-2481 - 2023
Jesse Beisegel, Ekkehard Köhler, Robert Schleicher, Martin Strehler
AbstractSolving problems on graphs dynamically calls for algorithms to function under repeated modifications to the graph and to be more efficient than solving the problem for the whole graph from scratch after each modification. Dynamic algorithms have been considered for several graph properties, for example connectivity, shortest paths and graph recognition. In this paper we present fully dynam... hiện toàn bộ
Quantum Algorithms for Weighing Matrices and Quadratic Residues
Springer Science and Business Media LLC - Tập 34 - Trang 413-428 - 2002
van Dam
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 Berns... hiện toàn bộ
Guest Editorial: Special Issue on Combinatorial Optimization and Applications
Springer Science and Business Media LLC - Tập 80 - Trang 1769-1770 - 2018
Zaixin Lu, Donghyun Kim
Improved computation of plane Steiner Minimal Trees
Springer Science and Business Media LLC - Tập 7 - Trang 219-229 - 1992
E. J. Cockayne, D. E. Hewgill
ASteiner Minimal Tree (SMT) for a given setA = {a 1,...,a n } in the plane is a tree which interconnects these points and whose total length, i.e., the sum of lengths of the branches, is minimum. To achieve the minimum, the tree may contain other points (Steiner points) besidesa 1,...,a n . Various improvements are presented to an earlier computer program of the authors for plane SMTs. These chang... hiện toàn bộ
Computing the Greedy Spanner in Near-Quadratic Time
Springer Science and Business Media LLC - Tập 58 - Trang 711-729 - 2009
Prosenjit Bose, Paz Carmi, Mohammad Farshi, Anil Maheshwari, Michiel Smid
The greedy algorithm produces high-quality spanners and, therefore, is used in several applications. However, even for points in d-dimensional Euclidean space, the greedy algorithm has near-cubic running time. In this paper, we present an algorithm that computes the greedy spanner for a set of n points in a metric space with bounded doubling dimension in $\ensuremath {\mathcal {O}}(n^{2}\log n)$ t... hiện toàn bộ
Optimal Point Movement for Covering Circular Regions
Springer Science and Business Media LLC - - 2013
Danny Z. Chen, Xuehou Tan, Haitao Wang, Gangshan Wu
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... hiện toàn bộ
Security of Quantum Key Distribution against All Collective Attacks
Springer Science and Business Media LLC - Tập 34 - Trang 372-388 - 2002
Biham, Boyer, Brassard, van de Graaf, Mor
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 of... hiện toàn bộ
Trade-Offs in Dynamic Coloring for Bipartite and General Graphs
Springer Science and Business Media LLC - Tập 85 - Trang 854-878 - 2022
Manas Jyoti Kashyop, N. S. Narayanaswamy, Meghana Nasre, Sai Mohith Potluri
The dynamic coloring problem has gained attention in the recent past. The focus has largely been on obtaining efficient update time algorithms using $$\Delta +1$$ or more colors and the trade-offs between update time and query time. Another important parameter in dynamic coloring is the number of recolorings per update which is addressed by the works of Barba et al. in WADS’17, and Solomon and Wei... hiện toàn bộ
Tổng số: 2,408   
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 10