ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

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 finding the jump number of a partial orber by substitution decomposition (1985)
    Springer
    Order 2 (1985), S. 9-23 
    Details
    ISSN: 1572-9273
    Keywords: 06A10 ; 68C25 ; Jump number ; substitution decomposition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Consider the linear extensions of a partial order. A jump occurs in a linear extension if two consecutive elements are unrelated in the partial order. The jump number problem is to find a linear extension of the ordered set which contains the smallest possible number of jumps. We discuss a decomposition approach for this problem from an algorithmic point of view. Based on this some new classes of partial orders are identified, for which the problem is polynomially solvable.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00337920
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders (1987)
    Springer
    Order 3 (1987), S. 359-367 
    Details
    ISSN: 1572-9273
    Keywords: 06A10 ; 68C25 ; Ordered set ; jump number ; matching ; dynamic programming ; bipartite permutation graphs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Let L=u 1 , u 2 , ..., u k be a linear extension of a poset P. Each pair (u i , u i+1 ) of unrelated elements in P is called a jump of L. The jump number problem is to find L with the minimum number of jumps. The problem is known to be NP-hard even on bipartite posets. Here we present a linear time algorithm for it in 2-dimensional bipartite posets. We also discuss briefly some weighted cases.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00340778
    Location Call Number Expected 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...