Browsing LCS Technical Memos (1974 - 2003) by Author "Shor, Peter"

Now showing items 1-2 of 2

    • Generalized Planar Matching 

      Berman, Fran; Leighton, Tom; Shor, Peter; Snyder, Larry (1985-04)
      In this paper, we prove that maximum planar H-matching (the problem of determining the maximum number of node-disjointed copies of the fixed graph H contained in a variable planar graph G) is NP-complete for any connected ...

    • Tight Bounds for Minimax Grid Matching, with Applications to the Average Case Analysis of Algorithms 

      Leighton, Tom; Shor, Peter (1986-05)
      The minimax grid matching problem is a fundamental combinatorial problem associated with the average case analysis of algorithms. The problem has arisen in a number of interesting and seemingly unrelated areas, including ...