Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Optimal coteries for rings and related networks (1995)
    Springer
    Distributed computing 8 (1995), S. 191-201 
    Details
    ISSN: 1432-0452
    Keywords: Coterie ; Availability ; Network ; Distributed system ; Mutual exclusion ; Quorum ; Ring ; Fault tolerance
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary Let a distributed system be represented by a graphG=(V, E), whereV is the set of nodes andE is the set of communication links. A coterie is defined as a family,C, of subsets ofV such that any pair of subsets inC has at least one node in common and no subset inC contains any other subset inC. Assuming that each nodev i ∈V (resp. linke j ∈E) is operational with probabilityp i (resp.r j ), the availability of a coterie is defined as the probability that the operational nodes and links ofG connect all nodes in at least one subset in the coterie. Although it is computationally intractable to find an optimal coterie that maximizes availability for general graphG, we show in this paper that, ifG is a ring, either a singleton coterie or a 3-majority coterie is optimal. Therefore, for any ring, an optimal coterie can be computed in polynomial time. This result is extended to the more general graphs, in which each biconnected component is either an edge or a ring.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02242737
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph (1992)
    Springer
    Algorithmica 7 (1992), S. 583-596 
    Details
    ISSN: 1432-0541
    Keywords: Undirected graphs ; Spanning subgraphs ; Connectivity ; k-edge-connectivity ; k-node-connectivity ; Linear-time algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show that anyk-connected graphG = (V, E) has a sparsek-connected spanning subgraphG′ = (V, E′) with ¦E′¦ =O(k¦V¦) by presenting anO(¦E¦)-time algorithm to find one such subgraph, where connectivity stands for either edge-connectivity or node-connectivity. By using this algorithm as preprocessing, the time complexities of some graph problems related to connectivity can be improved. For example, the current best time boundO(max{k 2¦V¦1/2,k¦V¦}¦E¦) to determine whether node-connectivityK(G) of a graphG = (V, E) is larger than a given integerk or not can be reduced toO(max{k 3¦V¦3/2,k 2¦V¦2}).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758778
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Chain packing in graphs (1991)
    Springer
    Algorithmica 6 (1991), S. 826-839 
    Details
    ISSN: 1432-0541
    Keywords: Graph algorithms ; Computational complexity ; Graph packing ; Chain packing ; Linear-time algorithms ; NP-completeness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper discusses the complexity of packingk-chains (simple paths of lengthk) into an undirected graph; the chains packed must be either vertex-disjoint or edge-disjoint. Linear-time algorithms are given for both problems when the graph is a tree, and for the edge-disjoint packing problem when the graph is general andk = 2. The vertex-disjoint packing problem for general graphs is shown to be NP-complete even when the graph has maximum degree three andk = 2. Similarly the edge-disjoint packing problem is NP-complete even when the graph has maximum degree four andk = 3.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759074
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A Fast Algorithm For Finding A Maximum Free Multiflow In An Inner Eulerian Network And Some Generalizations (1998)
    Springer
    Combinatorica 18 (1998), S. 61-83 
    Details
    ISSN: 1439-6912
    Keywords: AMS Subject Classification (1991) Classes:  90C27; 90B10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: be a network, where is an undirected graph with nodes and edges, is a set of specified nodes of , called terminals, and each edge of has a nonnegative integer capacity . If the total capacity of edges with one end at is even for every non-terminal node , then is called inner Eulerian. A free multiflow is a collection of flows between arbitrary pairs of terminals such that the total flow through each edge does not exceed its capacity. In this paper we first generalize a method in Karzanov [11] to find a maximum integer free multiflow in an inner Eulerian network, in time, where is the complexity of finding a maximum flow between two terminals. Next we extend our algorithm to solve the so-called laminar locking problem on multiflows, also in time. We then consider analogs of the above problems in inner balanced directed networks, which means that for each non-terminal node , the sums of capacities of arcs entering and leaving are the same. We show that for such a network a maximum integer free multiflow can be constructed in time, and then extend this result to the corresponding locking problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009811
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    A fast algorithm for computing minimum 3-way and 4-way cuts (2000)
    Springer
    Mathematical programming 88 (2000), S. 507-520 
    Details
    ISSN: 1436-4646
    Keywords: Key words: minimum cuts – graphs – hypergraphs –k-way cuts – polynomial algorithm – submodular function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n k-1 F(n,m))=O(mn k log(n 2 /m)) time and O(n 2) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound Õ(mn 3) for weighted graphs, but improves the bound Õ(mn 3) to O(n 2 F(n,m))=O(min{mn 8/3,m 3/2 n 2}) for unweighted graphs. The bound Õ(mn 4) for k=4 improves the previous best randomized bound Õ(n 6) (for m=o(n 2)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00011383
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Totally balanced combinatorial optimization games (2000)
    Springer
    Mathematical programming 87 (2000), S. 441-452 
    Details
    ISSN: 1436-4646
    Keywords: Key words: combinatorial optimization – duality theory – cooperative games – total balancedness ; Mathematics Subject Classification (1991): 90D12
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Combinatorial optimization games deal with cooperative games for which the value of every subset of players is obtained by solving a combinatorial optimization problem on the resources collectively owned by this subset. A solution of the game is in the core if no subset of players is able to gain advantage by breaking away from this collective decision of all players. The game is totally balanced if and only if the core is non-empty for every induced subgame of it.¶We study the total balancedness of several combinatorial optimization games in this paper. For a class of the partition game [5], we have a complete characterization for the total balancedness. For the packing and covering games [3], we completely clarify the relationship between the related primal/dual linear programs for the corresponding games to be totally balanced. Our work opens up the question of fully characterizing the combinatorial structures of totally balanced packing and covering games, for which we present some interesting examples: the totally balanced matching, vertex cover, and minimum coloring games.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050005
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Implementing an efficient minimum capacity cut algorithm (1994)
    Springer
    Mathematical programming 67 (1994), S. 325-341 
    Details
    ISSN: 1436-4646
    Keywords: Minimum capacity cut ; Network flow ; Polynomial algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, we present an efficient implementation of theO(mn + n 2 logn) time algorithm originally proposed by Nagamochi and Ibaraki (1992) for computing the minimum capacity cut of an undirected network. To enhance computation, various ideas are added so that it can contract as many edges as possible in each iteration. To evaluate the performance of the resulting implementation, we conducted extensive computational experiments, and compared the results with that of Padberg and Rinaldi's algorithm (1990), which is currently known as one of the practically fastest programs for this problem. The results indicate that our program is considerably faster than Padberg and Rinaldi's program, and its running time is not significantly affected by the types of the networks being solved.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582226
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Fractional knapsack problems (1977)
    Springer
    Mathematical programming 13 (1977), S. 255-271 
    Details
    ISSN: 1436-4646
    Keywords: Fractional knapsack problem ; Knapsack problem ; Greedy solution ; Integer programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The fractional knapsack problem to obtain an integer solution that maximizes a linear fractional objective function under the constraint of one linear inequality is considered. A modification of the Dinkelbach's algorithm [3] is proposed to exploit the fact that good feasible solutions are easily obtained for both the fractional knapsack problem and the ordinary knapsack problem. An upper bound of the number of iterations is derived. In particular it is clarified how optimal solutions depend on the right hand side of the constraint; a fractional knapsack problem reduces to an ordinary knapsack problem if the right hand side exceeds a certain bound.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584342
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    A globally convergent Newton method for solving strongly monotone variational inequalities (1993)
    Springer
    Mathematical programming 58 (1993), S. 369-383 
    Details
    ISSN: 1436-4646
    Keywords: Variational inequality problem ; Newton method ; global convergence ; quadratic convergence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Variational inequality problems have been used to formulate and study equilibrium problems, which arise in many fields including economics, operations research and regional sciences. For solving variational inequality problems, various iterative methods such as projection methods and the nonlinear Jacobi method have been developed. These methods are convergent to a solution under certain conditions, but their rates of convergence are typically linear. In this paper we propose to modify the Newton method for variational inequality problems by using a certain differentiable merit function to determine a suitable step length. The purpose of introducing this merit function is to provide some measure of the discrepancy between the solution and the current iterate. It is then shown that, under the strong monotonicity assumption, the method is globally convergent and, under some additional assumptions, the rate of convergence is quadratic. Limited computational experience indicates the high efficiency of the proposed method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581276
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Theoretical comparisons of search strategies in branch-and-bound algorithms (1976)
    Springer
    International journal of parallel programming 5 (1976), S. 315-344 
    Details
    ISSN: 1573-7640
    Keywords: Branch-and-bound ; search strategies ; best-bound search ; depth-first search ; breadth-first search ; heuristic search ; computational efficiency
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Four known search strategies used in branch-and-bound algorithms-heuristic search, depth-first search, best-bound search, and breadth-first search-are theoretically compared from the viewpoint of the performance of the resulting algorithms. Heuristic search includes the other three as special cases. Since heuristic search is determined by a heuristic functionh, we first investigate how the performance of the resulting algorithms depends onh. In particular, we show that heuristic search is stable in the sense that a slight change inh causes only a slight change in its performance. The “best” and the “worst” heurstic functions are clarified, and also discussed is how the heuristic functionh should be modified to obtain a branch-and-bound algorithm with an improved performance. Finally, properties and limitations of depth-first search, best-bound search, and breadth-first search viewed as special cases of heuristic search are considered. In particular, it is shown that the stability observed for heuristic search no longer holds for depth-first search.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00998631
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...