Faster Scaling Algorithms for General Graph Matching Problems

Abstract

This paper presents an algorithm for minimum cost matching on a general graph with integral edge costs, that runs in time close to the best known bound for cardinality matching. Specifically, let n, m and N denote the number of vertices, number of edges, and largest magnitude of a cost, respectively. Other applications of the new algorithm are given, including an efficient implementation of Christofides' traveling salesman approximation algorithm and efficient solutions to update problems that require the linear programming duals for matching. (KR)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 11, 1989
Accession Number
ADA215112

Entities

People

  • Harold N. Gabow
  • Robert Tarjan

Organizations

  • Princeton University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Computer Programming
  • Computer Science
  • Computers
  • Crossings
  • Efficiency
  • Errors
  • Inequalities
  • Integrals
  • Intervals
  • Iterations
  • Linear Programming
  • Lists (Data Structures)
  • New Jersey
  • Notation
  • Observation

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research