Abstract In order to simulate virtual agents in the replica of a real facility across a long time span, a crowd simulation engine needs a list of agent arrival and destination locations and times that reflect those seen in the actual facility. Working together with a major metropolitan transportation authority, we propose a specification that can be used to procedurally generate this information. This specification is both uniquely compact and expressive—compact enough to mirror the mental model of building managers and expressive enough to handle the wide variety of crowds seen in real urban environments. We also propose a procedural algorithm for generating tens of thousands of high-level agent paths from this specification. This algorithm allows our specification to be used with traditional crowd simulation obstacle avoidance algorithms while still maintaining the realism required for the complex, real-world simulations of a transit facility. Our evaluation with industry professionals shows that our approach is intuitive and provides controls at the right level of detail to be used in large facilities (200,000+ people/day).

Following work of Stroud and Saeger and Anand et al., we formulate a port of entry inspection sequencing task as a problem of finding an optimal binary decision tree for an appropriate Boolean decision function. We report on new algorithms that are more efficient computationally than those presented by Stroud and Saeger and Anand et al. We achieve these efficiencies through a combination of specific numerical methods for finding optimal thresholds for sensor functions and a novel binary decision tree search algorithm that operates on a space of potentially acceptable binary decision trees.

The span $\lambda$ (G) of a graph G is the smallest k for which G's vertices can be L(2,1)-colored, i.e., colored with integers in $\{0,1, \ldots, k \}$ so that adjacent vertices' colors differ by at least 2, and colors of vertices at distance two differ. G is full-colorable if some such coloring uses all colors in $\{0,1, \ldots, \lambda (G) \}$ and no others. We prove that all trees except stars are full-colorable. The connected graph G with the smallest number of vertices exceeding $\lambda$ (G) which is not full-colorable is C6. We describe an array of other connected graphs that are not full-colorable and go into detail on full-colorability of graphs of maximum degree four or less.

Abstract When (X, d) is a finite metric space and π = (x1, …, xk) ∈ Xk, a central element for π is an element x of X for which max{d (x, xi): i = 1, …, k} is minimum. The function that returns the set of all central elements for any tuple π is called the center function on X. In this article, the center function on finite trees is characterized. © John Wiley & Sons, Inc.

Role assignments, introduced by Everett and Borgatti [2], who called them role colorings, formalize the idea, arising in the theory of social networks, that individuals of the same social role will relate in the same way to the individuals playing counterpart roles. If 𝒢 is a graph, a k-role assignment is a function r mapping the vertex set onto the set of integers {1,2, … , k} so that if r(x) =r(y) then the sets of roles assigned to the neighbors of x and y are the same. We ask how hard it is to determine if a graph has a 2-role assignment and show that recognizing if a graph has a 2-role assignment is NP-complete. © 2001 John Wiley & Sons, Inc.

Abstract The stability of a (communication or transportation) network composed of (processing) nodes and (communication or transportation) links is of prime importance to network designers. As the network begins losing links or nodes, eventually, there is a loss in its effectiveness. Thus, it is desirable that networks be constructed to be as stable as possible, not only with respect to the initial disruption, but also with respect to the possible reconfiguration of the network after disruption. Many graph theoretical parameters have been used in the past to describe the stability of networks, including the vertex‐connectivity and edge‐connectivity, toughness and edge‐toughness, integrity and edge‐integrity, and tenacity. In this paper, we study the edge‐tenacity of graphs. We will be primarily interested in edge‐tenacious graphs, which can be considered very stable and are somewhat analogous in edge‐tenacity to honest graphs in edge‐integrity. We prove several results about edge‐tenacious graphs as well as find numerous classes of edge‐tenacious graphs.

Abstract We consider strongly connected orientations of the grid graph which has n1 + 1 eastwest avenues and n2 + 1 north–south streets. We seek optimal strongly connected orientations according to several different definitions of optimality. In earlier work, such optimal orientations were found for n1, n2 both at least 4 and for n1 = 1. Here we consider the case n1 = 2.

If $D = ( V,A )$ is a digraph, its p-competition graph for p a positive integer has vertex set V and an edge between x and y if and only if there are distinct vertices $a_1, \cdots ,a_p $ in D with $( x,a_i )$ and $( y,a_i )$ arcs of D for each $i = 1, \cdots ,p$. This notion generalizes the notion of ordinary competition graph, which has been widely studied and is the special case where $p = 1$. Results about the case where $p = 2$ are obtained. In particular, the paper addresses the question of which complete bipartite graphs are 2-competition graphs. This problem is formulated as the following combinatorial problem: Given disjoint sets A and B such that $| A \cup B | = n$, when can one find n subsets of $A \cup B$ so that every a in A and b in B are together contained in at least two of the subsets and so that the intersection of every pair of subsets contains at most one element from A and at most one element from B?

This paper considers a variety of combinatorial and number-theoretic questions that arise from considerations of uniqueness in the theory of measurement. Given $n + 1$ objects linearly ordered from worst (smallest) to best (largest), let $d_i $ stand for the difference between objects i and $i + 1$. Three types of assumptions that allow different inequality and equality comparisons between certain subsets of differences are considered. The three types of assumptions arise from problems concerning the uniqueness of finite algebraic difference measurement and finite subjective probability measurement. If the number of equality comparisons is sufficient to imply that the $d_i $ in $d = ( d_1 ,d_2 , \cdots ,d_n )$ are unique up to multiplication by a positive constant, then d is said to be unique. Results on the number of unique d’s and relationships among the components of such d’s are obtained for each of the three types.

The problem of finding strongly connected orientations (one-way street assignments) for graphs which arise from city streets is studied. Specifically, the grid graphs consisting of $n_1 + 1$ east-west avenues and $n_2 + 1$ north-south streets, for $n_1 ,n_2 $ sufficiently large, are studied. In general, it is difficult to find strongly connected orientations of graphs which are optimal according to any of a variety of criteria. However, for the grid graphs in question, optimal strongly connected orientations according to several important criteria are described. The results are surprising in that they improve significantly on the solution usually used in practice, namely: alternation of east and west orientations and north and south orientations.

Abstract An intersection assignment for a graph is the assignment of a set to each vertex so that edges correspond to pairs of sets which overlap. Intersection assignments are studied in which each set is a real interval, perhaps of specified minimum length. In particular, linear programming methods are used to see how to minimize the measure of the union of intervals in such an assignment, and how to maximize the sum of the lengths of the intervals in such an assignment. The results have application to a variety of scheduling problems.

Abstract This paper studies set assignments on graphs, functions assigning a set S(x) to each vertex x of a graph, and specifically set assignments where each set is a real interval, perhaps of specified minimum length. Such set assignments arise in applied problems dealing with fleet maintenance, mobile radio frequency assignment, task assignment, traffic phasing, banquet preparation, and computer storage optimization. These problems are briefly discussed. They are translated into problems of finding a set coloring [a set assignment in which an edge between x and y implies that S(x) and S(y) are disjoint], a set phasing [a set coloring of the complementary graph], or a set intersection assignment. The paper presents methods for finding set colorings, phasings, and intersection assignments in which the measure of the union of the intervals S(x) is minimized or in which the sum of the lengths of the S(x) is maximized.