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
    Perfect matchings in balanced hypergraphs (1996)
    Springer
    Combinatorica 16 (1996), S. 325-329 
    Details
    ISSN: 1439-6912
    Keywords: 05 C 65 ; 05 A 18 ; 05 C 70
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We generalize Hall's condition for the existence of a perfect matching in a bipartite graph, to balanced hypergraphs.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01261318
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Universally signable graphs (1997)
    Springer
    Combinatorica 17 (1997), S. 67-77 
    Details
    ISSN: 1439-6912
    Keywords: 05 C
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In a graph, a chordless cycle of length greater than three is called a hole. Let γ be a {0, 1} vector whose entries are in one-to-one correspondence with the holes of a graphG. We characterize graphs for which, for all choices of the vector γ, we can pick a subsetF of the edge set ofG such that |F ∪H| эγH (mod 2), for all holesH ofG and |F ∪T| э 1 for all trianglesT ofG. We call these graphsuniversally signable. The subsetF of edges is said to be labelledodd. All other edges are said to be labelledeven. Clearly graphs with no holes (triangulated graphs) are universally signable with a labelling of odd on all edges, for all choices of the vector γ. We give a decomposition theorem which leads to a good characterization of graphs that are universally signable. This is a generalization of a theorem due to Hajnal and Surányi [3] for triangulated graphs.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01196132
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    On the 0, 1 facets of the set covering polytope (1989)
    Springer
    Mathematical programming 43 (1989), S. 45-55 
    Details
    ISSN: 1436-4646
    Keywords: Set covering ; set packing ; polytope ; facet ; odd hole
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, we consider inequalities of the formΣ α jxj ≥ β, whereα j equals 0 or 1, andβ is a positive integer. We give necessary and sufficient conditions for such inequalities to define facets of the set covering polytope associated with a 0, 1 constraint matrixA. These conditions are in terms of critical edges and critical cutsets defined in the bipartite incidence graph ofA, and are in the spirit of the work of Balas and Zemel on the set packing problem where similar notions were defined in the intersection graph ofA. Furthermore, we give a polynomial characterization of a class of 0, 1 facets defined from chorded cycles of the bipartite incidence graph. This characterization also yields all the 0, 1 liftings of odd-hole inequalities for the simple plant location polytope.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582277
    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 matroid algorithm and its application to the efficient solution of two optimization problems on graphs (1988)
    Springer
    Mathematical programming 42 (1988), S. 471-487 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We address the problem of finding a minimum weight baseB of a matroid when, in addition, each element of the matroid is colored with one ofm colors and there are upper and lower bound restrictions on the number of elements ofB with colori, fori = 1, 2,⋯,m. This problem is a special case of matroid intersection. We present an algorithm that exploits the special structure, and we apply it to two optimization problems on graphs. When applied to the weighted bipartite matching problem, our algorithm has complexity O(|E∥V|+|V| 2log|V|). HereV denotes the node set of the underlying bipartite graph, andE denotes its edge set. The second application is defined on a general connected graphG = (V,E) whose edges have a weight and a color. One seeks a minimum weight spanning tree with upper and lower bound restrictions on the number of edges with colori in the tree, for eachi. Our algorithm for this problem has complexity O(|E∥V|+m 2 |V|+ m|V| 2). A special case of this constrained spanning tree problem occurs whenV * is a set of pairwise nonadjacent nodes ofG. One must find a minimum weight spanning tree with upper and lower bound restrictions on the degree of each node ofV *. Then the complexity of our algorithm is O(|V∥E|+|V * ∥V| 2). Finally, we discuss a new relaxation of the traveling salesman problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589417
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    The packing property (2000)
    Springer
    Mathematical programming 89 (2000), S. 113-126 
    Details
    ISSN: 1436-4646
    Keywords: Key words: clutter – packing property – Max-Flow Min-Cut property – minimally non ideal, total dual integrality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. A clutter (V, E) packs if the smallest number of vertices needed to intersect all the edges (i.e. a minimum transversal) is equal to the maximum number of pairwise disjoint edges (i.e. a maximum matching). This terminology is due to Seymour 1977. A clutter is minimally nonpacking if it does not pack but all its minors pack. An m×n 0,1 matrix is minimally nonpacking if it is the edge-vertex incidence matrix of a minimally nonpacking clutter. Minimally nonpacking matrices can be viewed as the counterpart for the set covering problem of minimally imperfect matrices for the set packing problem. This paper proves several properties of minimally nonpacking clutters and matrices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00011389
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    The traveling salesman problem on a graph and some related integer polyhedra (1985)
    Springer
    Mathematical programming 33 (1985), S. 1-27 
    Details
    ISSN: 1436-4646
    Keywords: Traveling Salesman Problem ; Integer Polyhedron ; Facet ; Graph ; Series-Parallel Graph ; Steiner Tree ; Polynomial Algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a graphG = (N, E) and a length functionl: E → ℝ, the Graphical Traveling Salesman Problem is that of finding a minimum length cycle goingat least once through each node ofG. This formulation has advantages over the traditional formulation where each node must be visited exactly once. We give some facet inducing inequalities of the convex hull of the solutions to that problem. In particular, the so-called comb inequalities of Grötschel and Padberg are generalized. Some related integer polyhedra are also investigated. Finally, an efficient algorithm is given whenG is a series-parallel graph.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582008
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Balanced 0, ±1-matrices, bicoloring and total dual integrality (1995)
    Springer
    Mathematical programming 71 (1995), S. 249-258 
    Details
    ISSN: 1436-4646
    Keywords: Combinatorial optimization ; Integrality of polyhedra ; Generalized set packing ; Covering
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A 0, ±1-matrixA is balanced if, in every submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of four. This definition was introduced by Truemper (1978) and generalizes the notion of a balanced 0, 1-matrix introduced by Berge (1970). In this paper, we extend a bicoloring theorem of Berge (1970) and total dual integrality results of Fulkerson, Hoffman and Oppenheim (1974) to balanced 0, ±1-matrices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01590956
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    A lift-and-project cutting plane algorithm for mixed 0–1 programs (1993)
    Springer
    Mathematical programming 58 (1993), S. 295-324 
    Details
    ISSN: 1436-4646
    Keywords: Cutting planes ; projection ; mixed 0–1 programming ; disjunctive programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose a cutting plane algorithm for mixed 0–1 programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most violated by the current fractional point. This cut is found through the solution of a linear program that has about twice the size of the usual LP relaxation. A lifting step is used to reduce the size of the LP's needed to generate the cuts. An additional strengthening step suggested by Balas and Jeroslow is then applied. We report our computational experience with a preliminary version of the algorithm. This approach is related to the work of Balas on disjunctive programming, the matrix cone relaxations of Lovász and Schrijver and the hierarchy of relaxations of Sherali and Adams.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581273
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Polyhedral study of the capacitated vehicle routing problem (1993)
    Springer
    Mathematical programming 60 (1993), S. 21-52 
    Details
    ISSN: 1436-4646
    Keywords: Vehicle routing ; polyhedron ; facet ; branch and cut
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The capacitated vehicle routing problem (CVRP) considered in this paper occurs when goods must be delivered from a central depot to clients with known demands, usingk vehicles of fixed capacity. Each client must be assigned to exactly one of the vehicles. The set of clients assigned to each vehicle must satisfy the capacity constraint. The goal is to minimize the total distance traveled. When the capacity of the vehicles is large enough, this problem reduces to the famous traveling salesman problem (TSP). A variant of the problem in which each client is visited by at least one vehicle, called the graphical vehicle routing problem (GVRP), is also considered in this paper and used as a relaxation of CVRP. Our approach for CVRP and GVRP is to extend the polyhedral results known for TSP. For example, the subtour elimination constraints can be generalized to facets of both CVRP and GVRP. Interesting classes of facets arise as a generalization of the comb inequalities, depending on whether the depot is in a handle, a tooth, both or neither. We report on the optimal solution of two problem instances by a cutting plane algorithm that only uses inequalities from the above classes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580599
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Book
    Book
    Integer programming and combinatorial optimization. Proceedings (1992)
    Details
    Title: Integer programming and combinatorial optimization. Proceedings
    Contributer: Balas, Egon , Cornuéjols, Gérard , Kannan, Ravi
    Year of publication: 1992
    Pages: 461 S.
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...