Bibliothek

X
feed icon rss

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
  • 1
    Digitale Medien
    Digitale Medien
    Generalized polymatroids and submodular flows (1988)
    Springer
    Mathematical programming 42 (1988), S. 489-563 
    Details
    ISSN: 1436-4646
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01589418
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 2
    Digitale Medien
    Digitale Medien
    A note on packing paths in planar graphs (1995)
    Springer
    Mathematical programming 70 (1995), S. 201-209 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Disjoint paths ; Joins ; Packing cuts
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01585937
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 3
    Digitale Medien
    Digitale Medien
    Increasing the rooted-connectivity of a digraph by one (1999)
    Springer
    Mathematical programming 84 (1999), S. 565-576 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Mathematics Subject Classification (1991): 05C70, 90C27
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/s101070050040
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 4
    Digitale Medien
    Digitale Medien
    Directed vertex-connectivity augmentation (1999)
    Springer
    Mathematical programming 84 (1999), S. 537-553 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Key words: connectivity of directed graphs – augmentation – polynomial algorithm Mathematics Subject Classification (1991): 05C40, 05C20, 90C27, 05C85
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/s101070050038
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 5
    Digitale Medien
    Digitale Medien
    Covering symmetric supermodular functions by graphs (1999)
    Springer
    Mathematical programming 84 (1999), S. 483-503 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Mathematics Subject Classification (1991): 05C70, 90C27
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/s101070050034
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 6
    Digitale Medien
    Digitale Medien
    Conservative weightings and ear-decompositions of graphs (1993)
    Springer
    Combinatorica 13 (1993), S. 65-81 
    Details
    ISSN: 1439-6912
    Schlagwort(e): 05 C 70 ; 05 C 75 ; 94 B 60
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01202790
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 7
    Digitale Medien
    Digitale Medien
    Packing paths in planar graphs (1990)
    Springer
    Combinatorica 10 (1990), S. 325-331 
    Details
    ISSN: 1439-6912
    Schlagwort(e): 05 C 10 ; 05 C 38 ; 90 B 10
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF02128668
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 8
    Buch
    Buch
    Connections in combinatorial optimization /; 38 (2011)
    Oxford :Oxford Univ. Pr.,
    Details
    Titel: Connections in combinatorial optimization /; 38
    Autor: Frank, András
    Verlag: Oxford :Oxford Univ. Pr.,
    Erscheinungsjahr: 2011
    Seiten: XXIII, 639 S. : , graph. Darst. ; , 24 cm
    Serie: Oxford lecture series in mathematics and its applications 38
    ISBN: 0-19-920527-2 , 978-0-19-920527-1
    Materialart: Buch
    Sprache: Englisch
    URL: http://www.zentralblatt-math.org/zmath/en/advanced/?q=an:pre05872866&format=complete
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    ZIB Katalog
    Zuse-Institut Berlin get availability status
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...