All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 14 of 14

Showing per page

Secret sharing schemes for ports of matroids of rank 3

Oriol Farràs (2020)

Kybernetika

A secret sharing scheme is ideal if the size of each share is equal to the size of the secret. Brickell and Davenport showed that the access structure of an ideal secret sharing scheme is determined by a matroid. Namely, the minimal authorized subsets of an ideal secret sharing scheme are in correspondence with the circuits of a matroid containing a fixed point. In this case, we say that the access structure is a matroid port. It is known that, for an access structure, being a matroid port is not...

Spanning trees with many or few colors in edge-colored graphs

Hajo Broersma, Xueliang Li (1997)

Discussiones Mathematicae Graph Theory

Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.

Symmetrized and continuous generalization of transversals

Martin Kochol (1996)

Mathematica Bohemica

The theorem of Edmonds and Fulkerson states that the partial transversals of a finite family of sets form a matroid. The aim of this paper is to present a symmetrized and continuous generalization of this theorem.

Currently displaying 1 – 14 of 14

Page 1