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
    A Simplified Õ(nm) Time Edge-Splitting Algorithm in Undirected Graphs (2000)
    Springer
    Algorithmica 26 (2000), S. 50-67 
    Details
    ISSN: 1432-0541
    Keywords: Key words. Undirected graph, Multigraph, Edge-connectivity, Edge splitting, Minimum cut, Polynomial algorithm, Deterministic algorithm.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Let G=(V,E) be a multigraph which has a designated vertex s ∈ V with an even degree. For two edges e 1 = (s,u 1 ) and e 2 = (s,u 2 ) , we say that a multigraph G' is obtained from G by splitting e 1 and e 2 at s if two edges e 1 and e 2 are replaced with a single edge (u 1 ,u 2 ) . It is known that all edges incident to s can be split without losing the edge-connectivity of G in V-s . This complete splitting plays an important role in solving many graph connectivity problems. The currently fastest algorithm for a complete splitting [14] runs in O(n(m+n log n) log n) time, where n = |V| and m is the number of pairs of vertices between which G has an edge. Their algorithm is first designed for Eulerian multigraphs, and then extended for general multigraphs. Although the part for Eulerian multigraphs is simple, the rest for general multigraphs is considerably complicated. This paper proposes a much simpler O(n(m+n log n) log n) time algorithm for finding a complete splitting. A new edge-splitting theorem derived from our algorithm is also presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004539910004
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Voltaic effect of the humidity of (Zn, Cu)O thin films deposited by R. F. Sputtering
    Amsterdam : Elsevier
    Thin Solid Films 189 (1990), S. 9-17 
    Details
    ISSN: 0040-6090
    Source: Elsevier Journal Backfiles on ScienceDirect 1907 - 2002
    Topics: Physics
    Type of Medium: Electronic Resource
    URL: http://linkinghub.elsevier.com/retrieve/pii/0040-6090(90)90021-5
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Analyses on the 2 and 3-Flip Neighborhoods for the MAX SAT (1999)
    Springer
    Journal of combinatorial optimization 3 (1999), S. 95-114 
    Details
    ISSN: 1573-2886
    Keywords: MAX SAT ; SAT ; local search ; neighborhood
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract For problems SAT and MAX SAT, local search algorithms are widely acknowledged as one of the most effective approaches. Most of the local search algorithms are based on the 1-flip neighborhood, which is the set of solutions obtainable by flipping the truth assignment of one variable. In this paper, we consider r-flip neighborhoods for r ≥ 2, and propose, for r = 2, 3, new implementations that reduce the number of candidates in the neighborhood without sacrificing the solution quality. For 2-flip (resp., 3-flip) neighborhood, we show that its expected size is O(n + m) (resp., O(m + t2n)), which is usually much smaller than the original size O(n2) (resp., O(n3)), where n is the number of variables, m is the number of clauses and t is the maximum number of appearances of one variable. Computational results tell that these estimates by the expectation well represent the real performance.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009873324187
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Preface (1995)
    Springer
    Annals of operations research 57 (1995), S. ix 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02099686
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    An implicit enumeration program for zero-one integer programming (1972)
    Springer
    International journal of parallel programming 1 (1972), S. 75-92 
    Details
    ISSN: 1573-7640
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper describes some techniques to improve the speed of the implicit enumeration method for solving zero-one integer programming problems. Among these techniques, the most powerful is the one of using a column vector which works as a tag for each inequality, indicating whether or not the inequality should be checked for the current partial solution. A new condition for underlining a variable and the concept of pseudo-underlining are also proposed. These techniques were implemented in the computer programil lip (ILLinois Integer Programming code). The computational results for different types of problems are discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01108520
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Using branch-and-bound algorithms to obtain suboptimal solutions (1983)
    Springer
    Mathematical methods of operations research 27 (1983), S. 177-202 
    Details
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Das Branch-and-Bound-Prinzip kann erfolgreich zur Lösung verschiedener kombinatorischer Optimierungsprobleme eingesetzt werden. In der Regel nimmt der Rechenaufwand jedoch sehr stark mit wachsender Problemgröße zu. Um dieser Schwierigkeit zu begegnen, werden folgende drei suboptimale Methoden oft in der Praxis angewendet: (1) Seien z der Zielfunktionswert der besten bekannten Lösung eines gegebenen Minimierungsproblems undg (P i ) eine untere Schranke für die Zielfunktion des Teilproblems Pi. Dann terminiereP i , fallsg (P i ) ⩾z−∃ (z) ist, wobei∃ (z) eine vorgegebene Fehlerschranke ist. (2) Beende die Rechnung, sobald T0 Teilprobleme bearbeitet worden sind, wobei T0 vorgegeben ist (Beschränkung der Rechenzeit). (3) Berücksichtige stets höchstensM 0 (eine vorgegebene Zahl) aktive Teilprobleme. Die übrigen Teilprobleme weiden ignoriert (Beschränkung des Speicherplatzes). Die Auswirkungen dieser drei Methoden auf die benötigte Rechenzeit und die erhaltenen suboptimalen Lösungen werden theoretisch und an Hand von Simulationen untersucht.
    Notes: Abstract The branch-and-bound principle is successful in solving various combinatorial optimization problems. In general, however, the computation time becomes excessive as the sizes of problems grow. To overcome this difficulty the following three suboptimal methods are often employed in practice. (1) Letz be the value of currently known best solution of a given minimization problem, and letg (P i ) be a lower bound on the objective value of partial problemP i . TerminateP i ifg (P i ) ⩾z−∃ (z), where∃ (z) is an allowance specified in advance. (2) Cut off the computation as soon as T0 partial problems are decomposed, where T0 is a prespecified positive integer. (3) Always take into account at mostM 0 (a given positive integer) number of active partial problems. The overflown partial problems are simply ignored. The effects of these methods on the computation time and the quality of obtained suboptimal solutions are investigated from both theoretical and simulation points of view.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01916914
    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...