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
    Generalized polymatroids and submodular flows (1988)
    Springer
    Mathematical programming 42 (1988), S. 489-563 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Polyhedra related to matroids and sub- or supermodular functions play a central role in combinatorial optimization. The purpose of this paper is to present a unified treatment of the subject. The structure of generalized polymatroids and submodular flow systems is discussed in detail along with their close interrelation. In addition to providing several applications, we summarize many known results within this general framework.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589418
    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 note on packing paths in planar graphs (1995)
    Springer
    Mathematical programming 70 (1995), S. 201-209 
    Details
    ISSN: 1436-4646
    Keywords: Disjoint paths ; Joins ; Packing cuts
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Seymour (1981) proved that the cut criterion is necessary and sufficient for the solvability of the edge-disjoint paths problem when the union of the supply graph and the demand graph is planar and Eulerian. When only planarity is required, Middendorf and Pfeiffer (1993) proved the problem to be NP-complete. For this case, Korach and Penn (1992) proved that the cut criterion is sufficient for the existence of a near-complete packing of paths. Here we generalize this result by showing how a natural strengthening of the cut criterion yields better packings of paths. Analogously to Seymour's approach, we actually prove a theorem on packing cuts in an arbitrary graph and then the planar edge-disjoint paths case is obtained by planar dualization. The main result is derived from a theorem of Sebő (1990) on the structure of ±1 weightings of a bipartite graph with no negative circuits.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585937
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Conservative weightings and ear-decompositions of graphs (1993)
    Springer
    Combinatorica 13 (1993), S. 65-81 
    Details
    ISSN: 1439-6912
    Keywords: 05 C 70 ; 05 C 75 ; 94 B 60
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A subsetJ of edges of a connected undirected graphG=(V, E) is called ajoin if |C∩J|≤|C|/2 for every circuitC ofG. Answering a question of P. Solé and Th. Zaslavsky, we derive a min-max formula for the maximum cardinality μ of a joint ofG. Namely, μ=(φ+|V|−1)/2 where φ denotes the minimum number of edges whose contraction leaves a factor-critical graph. To study these parameters we introduce a new decomposition ofG, interesting for its own sake, whose building blocks are factor-critical graphs and matching-covered bipartite graphs. We prove that the length of such a decomposition is always φ and show how an optimal join can be constructed as the union of perfect matchings in the building blocks. The proof relies on the Gallai-Edmonds structure theorem and gives rise to a polynomial time algorithm to construct the optima in question.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01202790
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Packing paths in planar graphs (1990)
    Springer
    Combinatorica 10 (1990), S. 325-331 
    Details
    ISSN: 1439-6912
    Keywords: 05 C 10 ; 05 C 38 ; 90 B 10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A generalization of P. Seymour's theorem on planar integral 2-commodity flows is given when the underlying graphG together with the demand graphH (a graph having edges that connect the corresponding terminal pairs) form a planar graph and the demand edges are on two faces ofG.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02128668
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Directed vertex-connectivity augmentation (1999)
    Springer
    Mathematical programming 84 (1999), S. 537-553 
    Details
    ISSN: 1436-4646
    Keywords: Key words: connectivity of directed graphs – augmentation – polynomial algorithm Mathematics Subject Classification (1991): 05C40, 05C20, 90C27, 05C85
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050038
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Increasing the rooted-connectivity of a digraph by one (1999)
    Springer
    Mathematical programming 84 (1999), S. 565-576 
    Details
    ISSN: 1436-4646
    Keywords: Mathematics Subject Classification (1991): 05C70, 90C27
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: In order to unify these approaches, here we describe a two-phase greedy algorithm working on a slight extension of lattice polyhedra. This framework includes the rooted node-connectivity augmentation problem, as well, and hence the resulting algorithm, when appropriately specialized, finds a minimum cost of new edges whose addition to a digraph increases its rooted connectivity by one. The only known algorithm for this problem used submodular flows. Actually, the specialized algorithm solves an extension of the rooted edge-connectivity and node-connectivity augmentation problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050040
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Covering symmetric supermodular functions by graphs (1999)
    Springer
    Mathematical programming 84 (1999), S. 483-503 
    Details
    ISSN: 1436-4646
    Keywords: Mathematics Subject Classification (1991): 05C70, 90C27
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050034
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Book
    Book
    Connections in combinatorial optimization /; 38 (2011)
    Oxford :Oxford Univ. Pr.,
    Details
    Title: Connections in combinatorial optimization /; 38
    Author: Frank, András
    Publisher: Oxford :Oxford Univ. Pr.,
    Year of publication: 2011
    Pages: XXIII, 639 S. : , graph. Darst. ; , 24 cm
    Series Statement: Oxford lecture series in mathematics and its applications 38
    ISBN: 0-19-920527-2 , 978-0-19-920527-1
    Type of Medium: Book
    Language: English
    URL: http://www.zentralblatt-math.org/zmath/en/advanced/?q=an:pre05872866&format=complete
    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...