Abstract Let be a hypergraph, where is a set of vertices and is a set of clusters , , such that the clusters in are not necessarily disjoint. This article considers the feasibility clustered traveling salesman problem, denoted by . In the we aim to decide whether a simple path exists that visits each vertex exactly once, such that the vertices of each cluster are visited consecutively. We focus on hypergraphs with no feasible solution path and consider removing vertices from clusters, such that the hypergraph with the new clusters has a feasible solution path for . The algorithm uses a PQ‐tree data structure and runs in linear time.

Abstract In this note, we prove that a collection of single bend paths on a grid, the so‐called B1 representations, have strong Helly number 4. This corrects a false claim from Ref. [Golumbic et al., Networks, 54 (2009), 130–138; and other errata are also corrected. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013

Abstract We combine the known notion of the edge intersection graphs of paths in a tree with a VLSI grid layout model to introduce the edge intersection graphs of paths on a grid. Let 𝒫 be a collection of nontrivial simple paths on a grid 𝒢. We define the edge intersection graph E P G (𝒫) of 𝒫 to have vertices which correspond to the members of 𝒫, such that two vertices are adjacent in E P G (𝒫) if the corresponding paths in 𝒫 share an edge in 𝒢. An undirected graph G is called an edge intersection graph of paths on a grid (EPG) if G = E P G (𝒫) for some 𝒫 and 𝒢, and 〈𝒫,𝒢〉 is an EPG representation of G . We prove that every graph is an EPG graph. A turn of a path at a grid point is called a bend. We consider here EPG representations in which every path has at most a single bend, called B 1 ‐EPG representations and the corresponding graphs are called B 1 ‐EPG graphs. We prove that any tree is a B 1 ‐EPG graph. Moreover, we give a structural property that enables one to generate non B 1 ‐EPG graphs. Furthermore, we characterize the representation of cliques and chordless 4‐cycles in B 1 ‐EPG graphs. We also prove that single bend paths on a grid have Strong Helly number 3. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009