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
    Polyhedral Results for Antimatroids (1989)
    Oxford, UK : Blackwell Publishing Ltd
    Annals of the New York Academy of Sciences 555 (1989), S. 0 
    Details
    ISSN: 1749-6632
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Natural Sciences in General
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/j.1749-6632.1989.tb22462.x
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Some Recent Results on Graph Matching (1989)
    Oxford, UK : Blackwell Publishing Ltd
    Annals of the New York Academy of Sciences 576 (1989), S. 0 
    Details
    ISSN: 1749-6632
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Natural Sciences in General
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/j.1749-6632.1989.tb16422.x
    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 integer points in polyhedra: A lower bound (1992)
    Springer
    Combinatorica 12 (1992), S. 135-142 
    Details
    ISSN: 1439-6912
    Keywords: 52 C 07 ; 11 H 06
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Given a polyhedronP⊂ℝ we writeP I for the convex hull of the integral points inP. It is known thatP I can have at most135-2 vertices ifP is a rational polyhedron with size φ. Here we give an example showing thatP I can have as many as Ω(ϕ n−1) vertices. The construction uses the Dirichlet unit theorem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01204716
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    The Colin de Verdière number and sphere representations of a graph (1997)
    Springer
    Combinatorica 17 (1997), S. 483-521 
    Details
    ISSN: 1439-6912
    Keywords: 05C
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Colin de Vedière introduced an interesting linear algebraic invariant μ(G) of graphs. He proved that μ(G)≤2 if and only ifG is outerplanar, and μ(G)≤3 if and only ifG is planar. We prove that if the complement of a graphG onn nodes is outerplanar, then μ(G)≥n−4, and if it is planar, then μ(G)≥n−5. We give a full characterization of maximal planar graphs whose complementsG have μ(G)=n−5. In the opposite direction we show that ifG does not have “twin” nodes, then μ(G)≥n−3 implies that the complement ofG is outerplanar, and μ(G)≥n−4 implies that the complement ofG is planar. Our main tools are a geometric formulation of the invariant, and constructing representations of graphs by spheres, related to the classical result of Koebe about representing planar graphs by touching disks. In particular we show that such sphere representations characterize outerplanar and planar graphs.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01195002
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Facets with fixed defect of the stable set polytope (2000)
    Springer
    Mathematical programming 88 (2000), S. 33-44 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. The stable set polytope of a graph is the convex hull of the 0-1 vectors corresponding to stable sets of vertices. To any nontrivial facet ∑ v∈V a(v)x v ≤b of this polytope we associate an integer δ, called the defect of the facet, by δ=∑ v∈V a(v)-2b. We show that for any fixed δ there is a finite collection of graphs (called “basis”) such that any graph with a facet of defect δ contains a subgraph which can be obtained from one of the graphs in the basis by a simple subdivision operation.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00011376
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Hit-and-run mixes fast (1999)
    Springer
    Mathematical programming 86 (1999), S. 443-461 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. It is shown that the “hit-and-run” algorithm for sampling from a convex body K (introduced by R.L. Smith) mixes in time O *(n 2 R 2/r 2), where R and r are the radii of the inscribed and circumscribed balls of K. Thus after appropriate preprocessing, hit-and-run produces an approximately uniformly distributed sample point in time O *(n 3), which matches the best known bound for other sampling algorithms. We show that the bound is best possible in terms of R,r and n.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050099
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Chip-Firing Games on Directed Graphs (1992)
    Springer
    Journal of algebraic combinatorics 1 (1992), S. 305-328 
    Details
    ISSN: 1572-9192
    Keywords: chip-firing game ; vector addition system ; reachability ; random walk ; probabilistic abacus ; Laplace operator ; Petri net
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We consider the following (solitary) game: each node of a directed graph contains a pile of chips. A move consists of selecting a node with at least as many chips as its outdegree, and sending one chip along each outgoing edge to its neighbors. We extend to directed graphs several results on the undirected version obtained earlier by the authors, P. Shor, and G. Tardos, and we discuss some new topics such as periodicity, reachability, and probabilistic aspects. Among the new results specifically concerning digraphs, we relate the length of the shortest period of an infinite game to the length of the longest terminating game, and also to the access time of random walks on the same graph. These questions involve a study of the Laplace operator for directed graphs. We show that for many graphs, in particular for undirected graphs, the problem whether a given position of the chips can be reached from the initial position is polynomial time solvable. Finally, we show how the basic properties of the “probabilistic abacus” can be derived from our results.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1022467132614
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Book
    Book
    Geometric algorithms and combinatorial optimization; 2 (1993)
    Berlin u.a. :Springer,
    Details
    Title: Geometric algorithms and combinatorial optimization; 2
    Author: Grötschel, Martin
    Contributer: Lovász, László , Schrijver, Alexander
    Edition: 2nd corr. ed.
    Publisher: Berlin u.a. :Springer,
    Year of publication: 1993
    Pages: 362 S.
    Series Statement: Algorithms and combinatorics 2
    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
  • 9
    Book
    Book
    Greedoids; 4 (1991)
    Berlin u.a. :Springer,
    Details
    Title: Greedoids; 4
    Author: Korte, Bernhard
    Contributer: Lovász, László , Schrader, Rainer
    Publisher: Berlin u.a. :Springer,
    Year of publication: 1991
    Pages: 211 S.
    Series Statement: Algorithms and combinatorics 4
    Type of Medium: Book
    URL: http://www.zbmath.org/?q=an:0733.05023
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
  • 10
    Book
    Book
    Geometric algorithms and combinatorial optimization; 2 (1988)
    Berlin u.a. :Springer,
    Details
    Title: Geometric algorithms and combinatorial optimization; 2
    Author: Grötschel, Martin
    Contributer: Lovász, László , Schrijver, Alexander
    Publisher: Berlin u.a. :Springer,
    Year of publication: 1988
    Pages: 362 S.
    Series Statement: Algorithms and combinatorics 2
    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...