Displaying similar documents to “Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP”

Square-root rule of two-dimensional bandwidth problem

Lan Lin, Yixun Lin (2011)

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

Similarity:

The bandwidth minimization problem is of significance in network communication and related areas. Let be a graph of vertices. The two-dimensional bandwidth () of is the minimum value of the maximum distance between adjacent vertices when is embedded into an  ×  grid in the plane. As a discrete optimization problem, determining () is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This...

A note on the Size-Ramsey number of long subdivisions of graphs

Jair Donadelli, Penny E. Haxell, Yoshiharu Kohayakawa (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Let  be the graph obtained from a given graph  by subdividing each edge  times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in (SODA 2002) 321–328], we prove that, for any graph , there exist graphs  with  edges that are Ramsey with respect to  .

Square-root rule of two-dimensional bandwidth problem

Lan Lin, Yixun Lin (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

The bandwidth minimization problem is of significance in network communication and related areas. Let be a graph of vertices. The two-dimensional bandwidth () of is the minimum value of the maximum distance between adjacent vertices when is embedded into an  ×  grid in the plane. As a discrete optimization problem, determining () is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This...

Analysis of a near-metric TSP approximation algorithm

Sacha Krug (2013)

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

Similarity:

The traveling salesman problem (TSP) is one of the most fundamental optimization problems. We consider the -metric traveling salesman problem ( -TSP), , the TSP restricted to graphs satisfying the -triangle inequality ({}) ≤ (({}) + ({})), for some cost function and any three vertices . The well-known path matching Christofides algorithm (PMCA) guarantees an approximation ratio of 3 /2 and is the best known algorithm for the -TSP, for 1 ≤  ≤ 2....

Repetition thresholds for subdivided graphs and trees

Pascal Ochem, Elise Vaslet (2012)

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

Similarity:

The introduced by Dejean and Brandenburg is the smallest real number such that there exists an infinite word over a -letter alphabet that avoids -powers for all   . We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.

Differential approximation of NP-hard problems with equal size feasible solutions

Jérôme Monnot (2010)

RAIRO - Operations Research

Similarity:

In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem  which only differ on a linear transformation of their objective functions. This...

Repetition thresholds for subdivided graphs and trees

Pascal Ochem, Elise Vaslet (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

The introduced by Dejean and Brandenburg is the smallest real number such that there exists an infinite word over a -letter alphabet that avoids -powers for all   . We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.