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
Filter
  • Articles: DFG German National Licenses  (3)
  • 2000-2004  (1)
  • 1995-1999  (2)
Source
Material
Years
Year
Keywords
  • 1
    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
  • 2
    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
  • 3
    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
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...