Browsing CS Technical Reports by Author "Terada, Routo"

Now showing items 1-3 of 3

An Almost Surely Optimal Algorithm for the Euclidean Traveling Salesman Problem

Halton, John; Terada, Routo (University of Wisconsin-Madison Department of Computer Sciences, 1978)
Fast Algorithms for NP-Hard Problems Which Are Optimal or Near-Optimal with Probability One

Terada, Routo (University of Wisconsin-Madison Department of Computer Sciences, 1979)

We present fast algorithms for six NP-hard problems. These algorithms are shown to be optimal or near-optimal with probability one (i.e., almost surely). First we design an algorithm for the Euclidean traveling salesman ...
Polynomial Time Algorithms for NP-Hard Problems Which Are Optimal or Near-Optimal With Probability One

Terada, Routo (University of Wisconsin-Madison Department of Computer Sciences, 1979)

This paper presents algorithms for five NP-hard problems: the vertex set cover of an undirected graph, the set cover of a collection of sets the clique of an undirected graph, the set packof a collection of sets, and the ...