Generalized Planar Matching.

Abstract

This paper proves that maximum planar H-matching (the problem of determining the maximum number of node-disjoint copies of the fixed graph H contained in a variable planar graph G) is NP-complete for any connected planar graph H with three or more nodes. It is also shown that perfect planar H-matching is NP-complete for any connected outerplanar graph H with three or more nodes, and is, somewhat surprisingly solvable in linear time for traingulated H with four or more nodes. The results generalize and unify several special-case results proved in the literature. The techniques can also be applied to solve a variety of problems, including the optimal tile salvage problem from wafer-scale integration. Although the authors prove that the optimal tile salvage problem and others like it are NP-complete, they also describe provably good approximation algorithms that are suitable for practical applications. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1985
Accession Number
ADA154809

Entities

People

  • F. Berman
  • L. Snyder
  • P. W. Shor
  • T. Leighton

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Air Platforms
  • Materials and Manufacturing Processes
  • Weapons Technologies

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Computer Science
  • Computers
  • Crossings
  • Embedding
  • Generators
  • Information Systems
  • Inverters
  • Mathematics
  • Polynomials
  • Security
  • Separators
  • Standards
  • Technical Information Centers
  • Transmission Lines
  • Triangles

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research