EuDML | Browse

The 3-Opt procedure deals with interchanging three edges of a tour with three edges not on that tour. For n≥6, the 3-Interchange Graph is a graph on 1/2(n-1)! vertices, corresponding to the hamiltonian tours in K_n; two vertices are adjacent iff the corresponding hamiltonian tours differ in an interchange of 3 edges; i.e. the tours differ in a single 3-Opt step. It is shown that the 3-Interchange Graph is a hamiltonian subgraph of the Symmetric Traveling Salesman Polytope. Upper bounds are derived...

Hard squares with negative activity and rhombus tilings of the plane.

Jonsson, Jakob (2006)

The Electronic Journal of Combinatorics [electronic only]

Hard squares with negative activity on cylinders with odd circumference.

Jonsson, Jakob (2009)

The Electronic Journal of Combinatorics [electronic only]

Hardness of embedding simplicial complexes in $ℝ^{d}$

Jiří Matoušek, Martin Tancer, Uli Wagner (2011)

Journal of the European Mathematical Society

Let ${𝙴𝙼𝙱𝙴𝙳}_{k \to d}$ be the following algorithmic problem: Given a ﬁnite simplicial complex $K$ of dimension at most $k$ , does there exist a (piecewise linear) embedding of $K$ into $ℝ^{d}$ ? Known results easily imply polynomiality of ${𝙴𝙼𝙱𝙴𝙳}_{k \to 2}$ ( $k = 1, 2$ ; the case $k = 1, d = 2$ is graph planarity) and of ${𝙴𝙼𝙱𝙴𝙳}_{k \to 2 k}$ for all $k \geq 3$ . We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that ${𝙴𝙼𝙱𝙴𝙳}_{d \to d}$ and ${𝙴𝙼𝙱𝙴𝙳}_{(d - 1) \to d}$ are undecidable for each $_{d} \geq 5$ . Our main result is NP-hardness of ${𝙴𝙼𝙱𝙴𝙳}_{2 \to 4}$ and, more generally, of ${𝙴𝙼𝙱𝙴𝙳}_{k \to d}$ for all $k$ , $d$ with...

We give a characterization of convex hypersurfaces with an equichordal point in terms of hedgehogs of constant width.

Currently displaying 1 – 20 of 52

Page 1 Next

Displaying 1 – 20 of 52

$H$ -convex Riemannian submanifolds.

$h^{*}$ -vectors, Eulerian polynomials and stable polytopes of graphs.

Haar spaces and polynomial selections.

Haar Type Orthonomal Wavelet Bases in R2.

Hajós' theorem and the partition lemma.

Halbierungssätze zur Gestaltabweichung ebener Figuren

Halfspace Range Search: An Algorithmic Application of k-Sets.

Halving point sets.

Hamiltonian Simple Polytopes.

Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem

Hard squares with negative activity and rhombus tilings of the plane.

Hard squares with negative activity on cylinders with odd circumference.

Hardness of embedding simplicial complexes in $ℝ^{d}$

Harmonic sum and duality.

Hearing the shape of a general convex domain: an extension to higher dimensions

Hedgehogs of constant width and equichordal points

Helly property associated with the discrete planes.

Helly-type theorems for infinite and for finite intersections of sets starshaped via staircase paths.

Helly-Type Theorems for Spheres.

Herissons et multiherissons (enveloppes parametrées par leur application de Gauss)

Currently displaying 1 – 20 of 52