R. M. Karp
U. V. Vazirani
- BeBoKaTaWi.S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson, "On the Power of Randomization in On-Line Algorithms', STOC 1990. Google Scholar
Digital Library
- CoGaJo.E. G. Coffman, M. R. Garey, D. S. Johnson, 'Dynamic Bin Packing', SIAM J. comput., vol 12, 1983, pp. 227-258.Google Scholar
- Gy,Le.A. Gyarfas, J. Lehel, 'Online and First Fit Colorings of Graphs', J. Graph theory, Vol. 12, No. 2, pp. 217- 227, 1988.Google Scholar
- Ku.T. G. Kurtz, "Solutions of Ordinary Differential Equations as Limits of Pure Jump Markov Processes', Journal of Applied Probability, vol. 7, 1970, pp. 49-58.Google ScholarCross Ref
- MaMcSl.M. Manasse, L.A. McGeoch, D. Sleator, "Competitive Algorithms for Online Problems', STOC 1988, pp.322-333. Google ScholarDigital Library
- Sl,Ta.D. Sleator, R.E. Tarjan, "Amortized Efficiency of List Update and Paging Rules', Comm. ACM, vol. 28, 1985, pp. 202-208. Google ScholarDigital Library
- Ya.A.C. Yao, "Probabilistic Computations: Towards a Unified Measure of Complexity', FOCS 1977, pp. 222- 227.Google Scholar
Index Terms
- An optimal algorithm for on-line bipartite matching
Recommendations
Matching graphs of hypercubes and complete bipartite graphs
Kreweras' conjecture [G. Kreweras, Matchings and hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996) 87-91] asserts that every perfect matching of the hypercube Q"d can be extended to a Hamiltonian cycle of Q"d. We [Jiri Fink, Perfect ...
Bipartite matching extendable graphs
Matching extendability is significant in graph theory and its applications. The basic notion in this direction is n-extendability introduced by Plummer in 1980. Motivated by the different natures of bipartite matchings and non-bipartite matchings, this ...
Maximum weight induced matching in some subclasses of bipartite graphs
AbstractA subset of edges of a graph is called a matching in G if no two edges in M share a common vertex. A matching M in G is called an induced matching if G[M], the subgraph of G induced by M, is the same as G[S], the subgraph of G induced ...
Comments