Library

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
    Oxford, UK : Blackwell Publishing Ltd
    Annals of the New York Academy of Sciences 555 (1989), S. 0 
    ISSN: 1749-6632
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Natural Sciences in General
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Oxford, UK : Blackwell Publishing Ltd
    Annals of the New York Academy of Sciences 576 (1989), S. 0 
    ISSN: 1749-6632
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Natural Sciences in General
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    Combinatorica 12 (1992), S. 135-142 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Combinatorica 17 (1997), S. 483-521 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 88 (2000), S. 33-44 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 86 (1999), S. 443-461 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 7
    Electronic Resource
    Electronic Resource
    Springer
    Journal of algebraic combinatorics 1 (1992), S. 305-328 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 8
    Book
    Book
    Philadelphia, PA :SIAM,
    Title: ¬An¬ algorithmic theory of numbers, graphs and convexity
    Author: Lovász, László
    Publisher: Philadelphia, PA :SIAM,
    Year of publication: 1989
    Pages: 91 S.
    Series Statement: CBMS-NSF regional conference series in applied mathematics
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 9
    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 ...
  • 10
    Title: Combinatorial optimization: papers from workshops held at DIMACS at Rutgers University Sept. 1992 - Aug. 1993; 20
    Contributer: Cook, William , Lovász, László , Seymour, Paul
    Publisher: Providence, RI :AMS,
    Year of publication: 1995
    Pages: 441 S.
    Series Statement: DIMACS Series in Discrete Mathematics and Theoretical Computer Science 20
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...