14343122
Backbone Colorings for Networks
We study backbone colorings, a variation on classical vertex colorings: Given a graph G=(V,E) and a spanning subgraph H (the backbone) of G, a backbone coloring for G and H is a proper vertex coloring V →{ 1,2,... } in which the colors assigned to adjacent vertices in H differ by at least two. We concentrate on the cases where the backbone is either a spanning tree or a spanning path.
15232467
Angle-Restricted Tours in the Plane
Abstract For a given set A ⊆ (− π ; + π ] of angles, the problem “Angle-Restricted Tour” (ART) is to decide whether a set P of n points in the Euclidean plane allows a closed directed tour consisting of straight line segments, such that all angles between consecutive line segments are from the set A . We present a variety of algorithmic and combinatorial results on this problem. In particular, we show that any finite set of at least five points allows a “pseudoconvex” tour (i.e., a tour where all angles are nonnegative), and we derive a fast algorithm for constructing such a tour. Moreover, we give a complete classification (from the computational complexity point of view) for the special cases where the tour has to be part of the orthogonal grid.
24984853
Detecting Cycles Through Three Fixed Vertices in a Graph
We present a simple linear time algorithm for finding a cycle through three fixed vertices in an undirected graph. The algorithm is based on decompositions into triconnected components and on a combinatorial result of Lovasz.
31641362
The toughness of split graphs
In this short note we argue that the toughness of split graphs can be computed in polynomial time. This solves an open problem from a recent paper by Kratsch et al. (Discrete Math. 150 (1996) 231–245).
39190998
Computing Maximum Valued Regions
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.
43889321
It is tough to be a plumber
In the Linux computer game KPlumber, the objective is to rotate tiles in a raster of squares so as to complete a system of pipes. We give a complexity classification for the original game and various special cases of it that arise from restricting the set of six possible tiles.Most of the cases are NP-complete. One polynomially solvable case is settled by formulating it as a perfect matching problem; other polynomial cases are settled by simple sweepline techniques. Moreover, we show that all the unsettled cases are polynomial time equivalent.
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.