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
    Book
    Book
    Matrices and matroids for systems analysis; 20 (2000)
    Berlin u.a. :Springer,
    Details
    Title: Matrices and matroids for systems analysis; 20
    Author: Murota, Kazuo
    Publisher: Berlin u.a. :Springer,
    Year of publication: 2000
    Pages: 483 S.
    Series Statement: Algorithms and combinatorics 20
    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
  • 2
    Electronic Resource
    Electronic Resource
    Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-Mcmillan form at infinity and structural indices in Kronecker form (1995)
    Springer
    Applicable algebra in engineering, communication and computing 6 (1995), S. 251-273 
    Details
    ISSN: 1432-0622
    Keywords: combinatorial matrix theory ; computer algebra ; determinant ; Kronecker form of matrix pencil ; matching ; polyhedral combinatorics ; Smith-McMillan form of rational matrix ; 05C50 ; 15A15 ; 68Q40 ; 68Q25
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics , Technology
    Notes: Abstract LetA(x)=(A ij (x)) be a matrix withA ij (x) being a polynomial or rational function inx. This paper proposes a “combinatorial relaxation” type algorithm for computing the highest degreeδ k (A) of a minor ofA(x) of a specified orderk. Such an algorithm can be used to compute the Smith-McMillan form of a rational function matrix at infinity, as well as the structure of the Kronecker form of a matrix pencil. The algorithm is based on a combinatorial upper bound $$\hat \delta _k (A)$$ onδ k (A), which is defined as the maximum weight of a matching of sizek in a bipartite graph associated withA. The algorithm is efficient, making full use of the fast algorithms for weighted matchings. It is combinatorial in almost all cases (or generically) and invokes algebraic elimination routines only when accidental numerical cancellations occur. The validity relies on the integrality of bipartite matching polytopes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01235719
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Parameter tuning and repeated application of the IMT-type transformation in numerical quadrature (1982)
    Springer
    Numerische Mathematik 38 (1982), S. 347-363 
    Details
    ISSN: 0945-3245
    Keywords: AMS(MOS): 65D30 ; CR: 5.16
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary The IMT rule, which is especially suited for the integration of functions with end-point singularities, is generalized by introducing parameters and also by repeatedly applying the parametrized IMT transformation. The quadrature formulas thus obtained are improved considerably both in efficiency and in robustness against end-point singularities. Asymptotic error estimates and numerical results are also given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01396437
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    On exchange axioms for valuated matroids and valuated delta-matroids (1996)
    Springer
    Combinatorica 16 (1996), S. 591-596 
    Details
    ISSN: 1439-6912
    Keywords: 05 B 35 ; 90 C 27
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Two further equivalent axioms are given for valuations of a matroid. Let M = (V,B) be a matroid on a finite setV with the family of basesB. For ω:B→R the following three conditions are equivalent: A similar result is obtained for valuations of a delta-matroid.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01271277
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Submodular Flow Problem with a Nonseparable Cost Function (1999)
    Springer
    Combinatorica 19 (1999), S. 87-109 
    Details
    ISSN: 1439-6912
    Keywords: AMS Subject Classification (1991) Classes:  90C35, 90C27, 90C10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004930050047
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Notes on L-/M-convex functions and the separation theorems (2000)
    Springer
    Mathematical programming 88 (2000), S. 129-146 
    Details
    ISSN: 1436-4646
    Keywords: Key words: L-convex functions – M-convex functions – integrally convex functions – submodularity – separation theorems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. The concepts of L-convex function and M-convex function have recently been introduced by Murota as generalizations of submodular function and base polyhedron, respectively, and discrete separation theorems are established for L-convex/concave functions and for M-convex/concave functions as generalizations of Frank’s discrete separation theorem for submodular/supermodular set functions and Edmonds’ matroid intersection theorem. This paper shows the equivalence between Murota’s L-convex functions and Favati and Tardella’s submodular integrally convex functions, and also gives alternative proofs of the separation theorems that provide a geometric insight by relating them to the ordinary separation theorem in convex analysis.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00011371
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Hierarchical decomposition of symmetric discrete systems by matroid and group theories (1993)
    Springer
    Mathematical programming 59 (1993), S. 377-404 
    Details
    ISSN: 1436-4646
    Keywords: 15A21 ; 20C35 ; 93A15 ; Combinatorial canonical form (CCF) ; group representation theory ; hierarchical decomposition ; large-scale system ; layered mixed (LM-) matrix ; matroid theory ; subsystem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An algebraic method is proposed for the hierarchical decomposition of large-scale group-symmetric discrete systems into partially ordered subsystems. It aims at extracting “substructures” and “hierarchy” for such systems as electrical networks and truss structures. The mathematical problem considered is: given a parametrized family of group invariant “structured” matricesA, we are to find two constant (=parameter-independent) nonsingular matricesS r andS c such thatS r -1 AS c takes a (common) block-triangular form. The proposed method combines two different decomposition principles developed independently in matroid theory and in group representation theory. The one is the decomposition principle for submodular functions, which has led to the Dulmage—Mendelsohn (DM-) decomposition and further to the combinatorial canonical form (CCF) of layered mixed (LM-) matrices. The other is the full reducibility of group representations, which yields the block-diagonal decomposition of group invariant matrices. The optimality of the proposed method is also discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581254
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Fenchel-type duality for matroid valuations (1998)
    Springer
    Mathematical programming 82 (1998), S. 357-375 
    Details
    ISSN: 1436-4646
    Keywords: Matroid intersection problem ; Fenchel duality ; Convex analysis ; Combinatorial optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The weighted matroid intersection problem has recently been extended to the valuated matroid intersection problem: Given a pair of valuated matroidsM i = (V, ℬ i , ω i ) (i = 1,2) defined on a common ground setV, find a common baseB ∈ ℬ 1 ∩ ℬ 2 that maximizesω 1 (B) + ω 2 (B). This paper develops a Fenchel-type duality theory related to this problem with a view to establishing a convexity framework for nonlinear integer programming. A Fenchel-type min max theorem and a discrete separation theorem are given. Furthermore, the subdifferentials of matroid valuations are investigated. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580075
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Combinatorial Relaxation Algorithm for the Maximum Degree of Subdeterminants: Computing Smith-McMillan Form at Infinity and Structura Indices in Kronecker Form (1995)
    Springer
    Applicable algebra in engineering, communication and computing 6 (1995), S. 251-273 
    Details
    ISSN: 1432-0622
    Keywords: Keywords: combinatorial matrix theory ; computer algebra ; determinant ; Kronecker form of matrix pencil ; matching ; polyhedral combinatorics ; Smith-McMillan form of rational matrix.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics , Technology
    Notes: Abstract.  Let A(x)=(A ij (x)) be a matrix with A ij (x) being a polynomial or rational function in x. This paper proposes a “combinatorial relaxation” type algorithm for computing the highest degree δ k (A) of a minor of A(x) of a specified order k. Such an algorithm can be used to compute the Smith-McMillan form of a rational function matrix at infinity, as well as the structure of the Kronecker form of a matrix pencil. The algorithm is based on a combinatorial upper bound * k (A) on δ k (A), which is defined as the maximum weight of a matching of size k in a bipartite graph associated with A. The algorithm is efficient, making full use of the fast algorithms for weighted matchings. It is combinatorial in almost all cases (or generically) and invokes algebraic elimination routines only when accidental numerical cancellations occur. The validity relies on the integrality of bipartite matching polytopes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01235719
    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...