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
    On the Complexity of Partial Order Properties (2000)
    Springer
    Order 17 (2000), S. 179-193 
    Details
    ISSN: 1572-9273
    Keywords: adversary ; evasiveness ; recognition complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The recognition complexity of ordered set properties is considered in terms of how many questions must be put to an adversary to decide if an unknown partial order has the prescribed property. We prove a lower bound of order n 2 for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable pairs, k ≤ n 2 / 4 we show that the recognition complexity is (n\choose 2). The complexity of interval orders is exactly (n\choose 2) - 1. We further establish bounds for being a lattice, being of height k and having width k.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1006422023869
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Decomposition of partial orders (1990)
    Springer
    Order 6 (1990), S. 335-350 
    Details
    ISSN: 1572-9273
    Keywords: 06A10 ; Boolean lattices ; partial orders ; split decomposition ; submodular functions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A decomposition theory for partial orders which arises from the split decomposition of submodular functions is introduced. As a consequence of this theory, any partial order has a unique decomposition consisting of indecomposable partial orders and certain highly decomposable partial orders. The highly decomposable partial orders are completely characterized. As a special case of partial orders, we consider lattices and distributive lattices. It occurs, that the highly decomposable distributive lattices are precisely the Boolean lattices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00346130
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    C++ im Nebenfachstudium: Konzepte und Erfahrungen (1996)
    Springer
    Informatik-Spektrum 19 (1996), S. 262-265 
    Details
    ISSN: 1432-122X
    Keywords: Schlüsselwörter  Informatikstudium im Nebenfach ; praktische Programmierausbildung ; C++ ; Didaktik ; Key words  Computer science as a minor subject ; training in practical programming ; C++ ; didactic issues
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s002870050037
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A linear-time algorithm for edge-disjoint paths in planar graphs (1995)
    Springer
    Combinatorica 15 (1995), S. 135-150 
    Details
    ISSN: 1439-6912
    Keywords: 05 C 85 ; 68 Q 35
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper we discuss the problem of finding edge-disjoint paths in a planar, undirected graph such that each path connects two specified vertices on the boundary of the graph. We will focus on the “classical” case where an instance additionally fulfills the so-calledevenness-condition. The fastest algorithm for this problem known from the literature requiresO (n 5/3(loglogn)1/3) time, wheren denotes the number of vertices. In this paper now, we introduce a new approach to this problem, which results in anO(n) algorithm. The proof of correctness immediately yields an alternative proof of the Theorem of Okamura and Seymour, which states a necessary and sufficient condition for solvability.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01294465
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Book review (1992)
    Springer
    Mathematical methods of operations research 36 (1992), S. 106-109 
    Details
    ISSN: 1432-5217
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01541036
    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...