Increasing Staff Completion of Civil Commitment Forms Through Instructions and Graphed Group Performance Feedback

ABSTRACT

A three-leg multiple baseline design across behaviors was used to assess the effects of an instruction-andfeedback package on correct completion of three required civil commitment forms by psychiatric emergency room personnel. The forms were for notices of rights, imminent harm applications, and witness lists. The intervention program consisted of an individualized training component and weekly group feedback via graphs. The instruction-and-feedback package produced immediate and significant increases in correct completion of all three commitment forms; the effects were maintained across six months of follow-up data collection. Discussion addressed the effectiveness of the package, the effects of participant drop-out, the functions of the instruction and feedback components of the package, and ethical concerns.     

Graph coloring by multiagent fusion search

A multiagent fusion search is presented for the graph coloring problem. In this method, each of agents performs the fusion search, involving a local search working in a primary exploitation role and a recombination search in a navigation role, with extremely limited memory and interacts with others through a decentralized protocol, thus agents are able to explore in parallel as well as to achieve a collective performance. As the knowledge components implemented with available structural information and in formalized forms, the Quasi-Tabu local search and grouping-based recombination rules are especially useful in addressing neutrality and ruggedness of the problem landscape. The new method has been tested on some hard benchmark graphs, and has been shown competitive in comparison with several existing algorithms. In addition, the method provides new lower bound solutions when applied to two large graphs. Some search characteristics of the proposed method is also discussed.     

Metric dimension of some distance-regular graphs

A resolving set of a graph is a set of vertices with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. In this paper, we construct a resolving set of Johnson graphs, doubled Odd graphs, doubled Grassmann graphs and twisted Grassmann graphs, respectively, and obtain the upper bounds on the metric dimension of these graphs.     

Disconnected $$g_c$$-critical graphs

Every critical graph is connected on proper edge-colorings of simple graphs. In contrast, there not only exist connected critical graphs but exist disconnected critical graphs on \(g_c\)-colorings of simple graphs. In this article, disconnected \(g_c\)-critical graphs are studied firstly and their structure characteristics are depicted.     

Half integer extreme points in the linear relaxation of the 2-edge-connected subgraph polyhedron

This paper studies the graphs for which the linear relaxation of the 2-connected spanning subgraph polyhedron has integer or half-integer extreme points. These graphs are called quasi-integer. For these graphs, the linear relaxation of the k-edge connected spanning subgraph polyhedron is integer for all k=4r, r≥1. The class of quasi-integer graphs is closed under minors and contains for instance the class of series-parallel graphs. We discuss some structural properties of graphs which are minimally non quasi-integer graphs, then we examine some basic operations which preserve the quasi-integer property. Using this, we show that the subdivisions of wheels are quasi-integer.     

Vertex and Tree Arboricities of Graphs

This paper studies the following variations of arboricity of graphs. The vertex (respectively, tree) arboricity of a graph G is the minimum number va(G) (respectively, ta(G)) of subsets into which the vertices of G can be partitioned so that each subset induces a forest (respectively, tree). This paper studies the vertex and the tree arboricities on various classes of graphs for exact values, algorithms, bounds, hamiltonicity and NP-completeness. The graphs investigated in this paper include block-cactus graphs, series-parallel graphs, cographs and planar graphs.     

Efficient identifications of structural similarities for graphs

Measuring and detecting graph similarities is an important topic with numerous applications. Early algorithms often incur quadratic time or higher, making them unsuitable for graphs of very large scales. Motivated by the cooling process of an object in a thermodynamic system, we devise a new method for measuring graph similarities that can be carried out in linear time. Our algorithm, called Random Walker Termination (RWT), employs a large number of random walkers to capture the structure of a given graph using termination rates in a time sequence. To verify the effectiveness of the RWT algorithm, we use three major graph models, namely, the Erd?s-Rényi random graphs, the Watts-Strogatz small-world graphs, and the Barabási-Albert preferential-attachment graphs, to generate graphs of different sizes. We show that the RWT algorithm performs well for graphs generated by these models. Our experiment results agree with the actual similarities of generated graphs. Using self-similarity tests, we show that RWT is sufficiently stable to generate consistent results. We use the graph edge rerouting test and the cross model test to demonstrate that RWT can effectively identify structural similarities between graphs.     

Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees

In this paper we consider the problem of partitioning complete multipartite graphs with edges colored by 2 colors into the minimum number of vertex disjoint monochromatic cycles, paths and trees, respectively. For general graphs we simply address the decision version of these three problems the 2-PGMC, 2-PGMP and 2-PGMT problems, respectively. We show that both 2-PGMC and 2-PGMP problems are NP-complete for complete multipartite graphs and the 2-PGMT problem is NP-complete for bipartite graphs. This also implies that all these three problems are NP-complete for general graphs, which solves a question proposed by the authors in a previous paper. Nevertheless, we show that the 2-PGMT problem can be solved in polynomial time for complete multipartite graphs. Research supported by NSFC.     

The Wiener index of Sierpiński-like graphs

Sierpiński-like graphs constitute an extensively studied family of graphs of fractal nature applicable in topology, mathematics of the Tower of Hanoi, computer science, and elsewhere. In this paper, we focus on the Wiener polarity index, Wiener index and Harary index of Sierpiński-like graphs. By Sierpiński-like graphs’ special structure and correlation, their Wiener polarity index and some Sierpiński-like graph’s Wiener index and Harary index are obtained.     

Fibonacci index and stability number of graphs: a polyhedral study

The Fibonacci index of a graph is the number of its stable sets. This parameter is widely studied and has applications in chemical graph theory. In this paper, we establish tight upper bounds for the Fibonacci index in terms of the stability number and the order of general graphs and connected graphs. Turán graphs frequently appear in extremal graph theory. We show that Turán graphs and a connected variant of them are also extremal for these particular problems. We also make a polyhedral study by establishing all the optimal linear inequalities for the stability number and the Fibonacci index, inside the classes of general and connected graphs of order n.     

Acyclically 3-colorable planar graphs

In this paper we study the acyclic 3-colorability of some subclasses of planar graphs. First, we show that there exist infinite classes of cubic planar graphs that are not acyclically 3-colorable. Then, we show that every planar graph has a subdivision with one vertex per edge that is acyclically 3-colorable and provide a linear-time coloring algorithm. Finally, we characterize the series-parallel graphs for which every 3-coloring is acyclic and provide a linear-time recognition algorithm for such graphs.     

Testing of the ‘reduction of compound alternatives’ principle

This paper reports an empirical investigation of the effects of three pictorial forms of problem representation on conformance with the Reduction of Compound Alternatives Principle of expected utility theory. The most common form of representation, written problem statements, was compared with three pictorial representations: tubes containing one hundred labeled balls, decision matrices with each column proportional in size to the probability of the corresponding event, and bar graphs. The tubes representation led to fewer violations of the Principle. In addition, when subjects were trained to construct proportional matrices from written problem statements, they exhibited fewer violations than those who received the same problems already formatted in proportional matrices. The results reported here should contribute to the development of a theory of the way people frame decision problems.     

Approximation of knapsack problems with conflict and forcing graphs

We study the classical 0–1 knapsack problem with additional restrictions on pairs of items. A conflict constraint states that from a certain pair of items at most one item can be contained in a feasible solution. Reversing this condition, we obtain a forcing constraint stating that at least one of the two items must be included in the knapsack. A natural way for representing these constraints is the use of conflict (resp. forcing) graphs. By modifying a recent result of Lokstanov et al. (Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA, pp 570–581, 2014) we derive a fairly complicated FPTAS for the knapsack problem on weakly chordal conflict graphs. Next, we show that the techniques of modular decompositions and clique separators, widely used in the literature for solving the independent set problem on special graph classes, can be applied to the knapsack problem with conflict graphs. In particular, we can show that every positive approximation result for the atoms of prime graphs arising from such a decomposition carries over to the original graph. We point out a number of structural results from the literature which can be used to show the existence of an FPTAS for several graph classes characterized by the exclusion of certain induced subgraphs. Finally, a PTAS for the knapsack problem with H-minor free conflict graph is derived. This includes planar graphs and, more general, graphs of bounded genus. The PTAS is obtained by expanding a general result of Demaine et al. (Proceedings of 46th annual IEEE symposium on foundations of computer science, FOCS 2005, pp 637–646, 2005). The knapsack problem with forcing graphs can be transformed into a minimization knapsack problem with conflict graphs. It follows immediately that all our FPTAS results of the current and a previous paper carry over from conflict graphs to forcing graphs. In contrast, the forcing graph variant is already inapproximable on planar graphs.     

The thickness of the complete multipartite graphs and the join of graphs

The thickness of a graph is the minimum number of planar spanning subgraphs into which the graph can be decomposed. It is known for relatively few classes of graphs, compared to other topological invariants, e.g., genus and crossing number. For the complete bipartite graphs, Beineke et al. (Proc Camb Philos Soc 60:1–5, 1964) gave the answer for most graphs in this family in 1964. In this paper, we derive formulas and bounds for the thickness of some complete k-partite graphs. And some properties for the thickness for the join of two graphs are also obtained.     

The <Emphasis Type="Italic">p</Emphasis>-maxian problem on block graphs

This paper deals with the p-maxian problem on block graphs with unit edge length. It is shown that the two points with maximum distance provide an optimal solution for the 2-maxian problem of block graphs except for K ₃. It can easily be extended to the p-maxian problem of block graphs. So we solve the p-maxian problem on block graphs in linear time.     

The second largest number of maximal independent sets in connected graphs with at most one cycle

A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we determine the second largest number of maximal independent sets among all graphs (respectively, connected graphs) of order n??4 with at most one cycle. We also characterize those extremal graphs achieving these values.     

A rearrangement of adjacency matrix based approach for solving the crossing minimization problem

In this paper, we first present a binary linear programming formulation for the crossing minimization problem (CMP) in bipartite graphs. Then we use the models of a modified minimum cost flow problem (MMCF) and a travelling salesman problem (TSP) to approximatively solve the CMP by rearranging the adjacency matrix of the bipartite graph. Our approaches are useful for problems defined on dense bipartite graphs. In addition, we compute the exact crossing numbers for some general dense graphs.     

Embeddings of circulant networks

In this paper we solve the edge isoperimetric problem for circulant networks and consider the problem of embedding circulant networks into various graphs such as arbitrary trees, cycles, certain multicyclic graphs and ladders to yield the minimum wirelength.     

An Evaluation of Staff Preference for Graphic Characteristics

The purpose of the current study was to assess staff preference for how data were displayed on graphs. Specifically, preference for line versus bar graphs was assessed, as well as preference for data displayed as one date in time versus multiple dates showing performance trends. A secondary purpose of the study was to assess staff comprehension of the data presented across different graphic displays. Participants included 60 entry-level direct care staff and 25 seasoned therapists. Therapists had more advanced training in applied behavior analysis than the direct care staff. The vast majority of direct care staff preferred data depicted as a bar graph versus data depicted as a line graph, even preferring a single bar graph over a time-series line graph. The therapists preferred time-series line graphs to bar graphs. Most staff demonstrated understanding of the data, regardless of how it was depicted.     

On total and edge coloring some Kneser graphs

Journal of Combinatorial Optimization - In this work, we investigate the total and edge colorings of the Kneser graphs K(n,&nbsp;s). We prove that the sparse case of Kneser graphs, the odd...