EuDML | Browse

Page 1

Displaying 1 – 10 of 10

Implicitly Representing Arrangements of Lines or Segments.

H. Edelsbrunner, Raimund Seidel, Micha Sharir, Leonidas Guibas, John Hershberger, Jack, Welzl, Emo Snoeyink (1989)

Discrete & computational geometry

Improved Bounds on Weak e-Nets for Convex Sets.

H. Edelsbrunner, B. Chazelle, E. Welzl, M. Sharir, L. Guibas, M. Grigni (1995)

Discrete & computational geometry

Improved lower bounds on the approximability of the traveling salesman problem

Hans-Joachim Böckenhauer, Sebastian Seibert (2000)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Improved Lower Bounds on the Approximability of the Traveling Salesman Problem

Hans-Joachim Böckenhauer, Sebastian Seibert (2010)

RAIRO - Theoretical Informatics and Applications

This paper deals with lower bounds on the approximability of different subproblems of the Traveling Salesman Problem (TSP) which is known not to admit any polynomial time approximation algorithm in general (unless $𝒫 = 𝒩𝒫$ ). First of all, we present an improved lower bound for the Traveling Salesman Problem with Triangle Inequality, Delta-TSP for short. Moreover our technique, an extension of the method of Engebretsen [11], also applies to the case of relaxed and sharpened triangle inequality, respectively,...

Incremental DFA minimisation

Marco Almeida, Nelma Moreira, Rogério Reis (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We present a new incremental algorithm for minimising deterministic finite automata. It runs in quadratic time for any practical application and may be halted at any point, returning a partially minimised automaton. Hence, the algorithm may be applied to a given automaton at the same time as it is processing a string for acceptance. We also include some experimental comparative results.