22610152
Counting k-Subsets and Convex k-gons in the Plane
We consider problems of the following type: Let S be a set of n points in the plane, let p be some point in S and let K be an integer, 3≤k≤n. We show how to compute the overall number of convex k-gons with corners at points in S, for any fixed k≥4.
15492927
Counting Convex Polygons in Planar Point Sets
Given a set S of n points in the plane, we compute in time O(n3) the total number of convex polygons whose vertices are a subset of S. We give an O(m · n3) algorithm for computing the number of convex k-gons with vertices in S, for all values k = 3,…, m; previously known bounds were exponential (O(nk/2). We also compute the number of empty convex polygons (resp.,k-gons, k m) with vertices in S in time O(n3) (resp., O(m · n3)).
25160918
Radio Labeling with Pre-assigned Frequencies
A radio labeling of a graph G is an assignment of pairwise distinct, positive integer labels to the vertices of G such that labels of adjacent vertices differ by at least 2. The radio labeling problem (RL) consists in determining a radio labeling that minimizes the maximum label that is used (the so-called span of the labeling). RL is a well-studied problem, mainly motivated by frequency assignment problems in which transmitters are not allowed to operate on the same frequency channel. We consider the special case where some of the transmitters have preassigned operating frequency channels. This leads to the natural variants P-RL(l) and P-RL(*) of RL with l pre-assigned labels and an arbitrary number of pre-assigned labels, respectively.We establish a number of combinatorial, algorithmical, and complexity-theoretical results for these variants of radio labeling. In particular, we investigate a simple upper bound on the minimum span, yielding a linear time approximation algorithm with a constant additive error bound for P-RL(*) restricted to graphs with girth ? 5. We consider the complexity of P-RL(l) and P-RL(*) for several cases in which RL is known to be polynomially solvable. On the negative side, we prove that P-RL(*) is NP-hard for cographs and for k-colorable graphs where a k-coloring is given (k ? 3). On the positive side, we derive polynomial time algorithms solving P-RL(*) and P-RL(l) for graphs with bounded maximum degree, and for solving P-RL(l) for k-colorable graphs where a k-coloring is given.
206844941
Pseudo-Hamiltonian Graphs
A pseudo-h-hamiltonian cycle in a graph is a closed walk that visits every vertex exactly h times. We present a variety of combinatorial and algorithmic results on pseudo- h-hamiltonian cycles: First, we show that deciding whether a graph is pseudo-h-hamiltonian is NP-complete for any given h ≥ 1. Surprisingly, deciding whether there exists an h ≥ 1 such that the graph is pseudo-h-hamiltonian, can be done in polynomial time. We also present sufficient conditions for pseudo- h-hamiltonicity that are based on stable sets and on toughness. Moreover, we investigate the computational complexity of finding pseudo-h-hamiltonian cycles on special graph classes like bipartite graphs, split graphs, planar graphs, cocomparability graphs; in doing this, we establish a precise separating line between easy and difficult cases of this problem.