Vés al contingut (premeu Retorn)

On-line matching in regular bipartite graphs

Barriere, E.; Muñoz, X.
Tipus d'activitat
Presentació treball a congrés
Nom de l'edició
22nd International Colloquium on Structural Information and Communication Complexity
Any de l'edició
Data de presentació
In an online problem, the input is revealed one step at a time. At every step, the online algorithm has to produce part of the output, based on the partial knowledge of the input. Such decisions are irrevocable, and thus online algorithms usually lead to a non optimal solution. The quality of an online algorithm is measured by its competitive ratio, which compares its performance with that of an optimal offline algorithm. The online bipartite matching problem has been studied since a first paper...
Paraules clau
bipartite graph, matching, on-line algorithm, regular graph
Grup de recerca
COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions