Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs
verfasst von : C. Gregory Plaxton
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
G
denote an
n
-vertex two-directional orthogonal ray graph. A bicolored 2D representation of
G
requires only
O
(
n
) space, regardless of the number of edges in
G
. Given such a compact representation of
G
, and a (possibly negative) weight for each vertex, we show how to compute a maximum weight matching of
G
in
O
(
n
log
2
n
) time. The classic problem of scheduling weighted unit tasks with release times and deadlines is a special case of this problem, and we obtain an
O
(
n
log
n
) time bound for this special case. As an application of our more general result, we obtain an
O
(
n
log
2
n
)-time algorithm for computing the VCG outcome of a sealed-bid unit-demand auction in which each item has two associated numerical parameters (e.g., third-party “quality” and “seller reliability” scores) and each bid specifies the amount an agent is willing to pay for any item meeting specified lower bound constraints with respect to these two parameters.