Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Maximum Semi-Matching Problem in Bipartite Graphs

100%

Katrenič J., Semanišin G.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 3

559-569

An (f, g)-semi-matching in a bipartite graph G = (U ∪ V,E) is a set of edges M ⊆ E such that each vertex u ∈ U is incident with at most f(u) edges of M, and each vertex v ∈ V is incident with at most g(v) edges of M. In this paper we give an algorithm that for a graph with n vertices and m edges, n ≤ m, constructs a maximum (f, g)-semi-matching in running time O(m ⋅ min [...] ) Using the reduction of [5] our result on maximum (f, g)-semi-matching problem directly implies an algorithm for the optimal semi-matching problem with running time O( [...] log n).

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Katrenič J.

1 Semanišin G.

1 2013

Wyniki wyszukiwania

Maximum Semi-Matching Problem in Bipartite Graphs