Author name cluster

Oded Kariv

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

STOC Conference 1978 Conference Paper

Algorithms for Edge Coloring Bipartite Graphs

Harold N. Gabow
Oded Kariv

A minimum edge coloring of a bipartite graph is a partition of the edges into Δ matchings, where Δ is the maximum degree in the graph. Coloring algorithms are presented that use time O(min(¦E¦ Δ log n, ¦E¦ @@@@n log n, n 2 log Δ)) and space O(nΔ). This compares favorably to the previous O(¦E¦ [equation] log Δ) time bound. The coloring algorithms also find maximum matchings on regular (or semi-regular) bipartite graphs. The time bounds compare favorably to the O(¦E&brvbar @@@@n) matching algorithm, expect when [equation] ≤ Δ ≤ @@@@n log n.

Details

FOCS Conference 1975 Conference Paper

An O(n^2. 5) Algorithm for Maximum Matching in General Graphs

Shimon Even
Oded Kariv

This work presents a new efficient algorithm for finding a maximum matching in an arbitrary graph. Two implementations are suggested, the complexity of the first is O(n2. 5) and the complexity of the second is O(m√n·log n) where n, m are the numbers of the vertices and the edges in the graph.

Details