An unexpected meeting of four seemingly unrelated problems: graph testing, DNA complex screening, superimposed codes and secure key distribution

This paper discusses the relation among four problems: graph testing, DNA complex screening, superimposed codes and secure key distribution. We prove a surprising equivalence relation among these four problems, and use this equivalence to improve current results on graph testing. In the rest of this paper, we give a lower bound for the minimum number of tests on DNA complex screening model. The first and second author would like to dedicate this paper to professor Frank K. Hwang on the occasion of his 65th birthday. This research is partially supported by Republic of China, National Science Council grant NSC 92-2115-M-009-014.     

Generalized median graphs and applications

We study the so-called Generalized Median graph problem where the task is to construct a prototype (i.e., a ‘model’) from an input set of graphs. While our primary motivation comes from an important biological imaging application, the problem effectively captures many vision (e.g., object recognition) and learning problems, where graphs are increasingly being adopted as a powerful representation tool. Existing techniques for his problem are evolutionary search based; in this paper, we propose a polynomial time algorithm based on a linear programming formulation. We propose an additional algorithm based on a bi-level method to obtain solutions arbitrarily close to the optimal in (worst case) non-polynomial time. Within this new framework, one can optimize edit distance functions that capture similarity by considering vertex labels as well as he graph structure simultaneously. We first discuss experimental evaluations in context of molecular image analysis problems—he methods will provide the basis for building a topological map of all 23 pairs of the human chromosome. Later, we include (a) applications to other biomedical problems and (b) evaluations on a public pattern recognition graph database. This work was supported by NSF grants CCF-0546509, IIS-0713489, and NIH grant GM 072131-23. The second author was also supported in part by the Department of Biostatistics and Medical Informatics, UW-Madison and UW ICTR, funded through an NIH Clinical and Translational Science Award (CTSA), grant number 1 UL1 RR025011.     

Steiner systems for two-stage disjunctive testing

The subject of this paper are some constructions of Steiner designs with blocks of two sizes that differ by one. The study of such designs is motivated by a combinatorial lower bound on the minimum number of individual tests at the second stage of a 2-stage disjunctive testing algorithm.     

Development of an algorithm for the application of Group Technology in the design of Manufacturing Systems

The Group Technology theory identifies and groups similar parts into families and machines into cells, advantages being in the similarity of the parts made in each cell, and designing and manufacturing. The benefits are: simple material flow, cost reduction in material handling, reduction in work in progress, reduction in the cycle time and set-up time, increased manufacturing flexibility, increased quality, and increased job satisfaction. The objective of the work presented in this paper was to develop a Group Technology (GT) algorithm by means of cell analysis for the design of the productive system to batch production, e.g. water heater manufacturing, system manufacturing, lathes manufacturing, etc. The TGIP algorithm allows the definition of technical and economical parameters for the application of Group Technology, also taking into account the demand for the performance of the algoof heating gasrithm. The benefits of the algorithm developed are the focus on solving the case of multiple machines and the assignment of the parts to the groups related to the load of the machines; also it allows the definition of technical and economical parameters to differentiate the machines that do the same operation or even the consideration of the demand for a certain period of time.     

Hypothesis group testing for disjoint pairs

Classical group testing (CGT) is a widely applicable biotechnical technique used to identify a small number of distinguished objects from a population when the presence of any one of these distinguished objects among a group of others produces an observable result. This paper discusses a variant of CGT called group testing for disjoint pairs (GTAP). The difference between the two is that in GTDP, the distinguished items are pairs from, not individual objects in, the population. There are several biological examples of when this abstract model applies. One biological example is DNA hybridization. The presence of pairs of hybridized DNA strands can be detected in a pool of DNA strands. Another situation is the detection of binding interactions between prey and bait proteins. This paper gives a random pooling method, similar in spirit to hypothesis testing, which identifies pairs of objects from a population that collectively have an observable function. This method is simply to apply, achieves good results, is amenable to automation and can be easily modified to compensate for testing errors. M.A. Bishop is supported by AFOSR FA8750-06-C-0007. A.J. Macula is supported by NSF-0436298, AFOSR FA8750-06-C-0007.     

A survey on nonadaptive group testing algorithms through the angle of decoding

Group testing, sometimes called pooling design, has been applied to a variety of problems such as blood testing, multiple access communication, coding theory, among others. Recently, screening experiments in molecular biology has become the most important application. In this paper, we review several models in this application by focusing on decoding, namely, giving a comparative study of how the problem is solved in each of these models.     

Probabilistic graph-coloring in bipartite and split graphs

We revisit in this paper the stochastic model for minimum graph-coloring introduced in (Murat and Paschos in Discrete Appl. Math. 154:564–586, 2006), and study the underlying combinatorial optimization problem (called probabilistic coloring) in bipartite and split graphs. We show that the obvious 2-coloring of any connected bipartite graph achieves standard-approximation ratio 2, that when vertex-probabilities are constant probabilistic coloring is polynomial and, finally, we propose a polynomial algorithm achieving standard-approximation ratio 8/7. We also handle the case of split graphs. We show that probabilistic coloring is NP-hard, even under identical vertex-probabilities, that it is approximable by a polynomial time standard-approximation schema but existence of a fully a polynomial time standard-approximation schema is impossible, even for identical vertex-probabilities, unless P=NP. We finally study differential-approximation of probabilistic coloring in both bipartite and split graphs. Part of this research has been performed while the second author was with the LAMSADE on a research position funded by the CNRS.     

Distance graphs on R n with 1-norm

Suppose S is a subset of a metric space X with metric d. For each subset D⊆{d(x,y):x,y∈S,x≠y}, the distance graph G(S,D) is the graph with vertex set S and edge set E(S,D)={xy:x,y∈S,d(x,y)∈D}. The current paper studies distance graphs on the n-space R ₁ ⁿ with 1-norm. In particular, most attention is paid to the subset Z ₁ ⁿ of all lattice points of R ₁ ⁿ . The results obtained include the degrees of vertices, components, and chromatic numbers of these graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Supported in part by the National Science Council under grant NSC-94-2115-M-002-015. Taida Institue for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.     

On broadcasting in unicyclic graphs

Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Finding the broadcast time of a vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for trees. In this paper we present a linear algorithm that determines the broadcast time of any originator in an arbitrary unicyclic graph. As a byproduct, we find a broadcast center of the unicyclic graph. We also present an O(|V|+k ²) algorithm to find the broadcast time of an arbitrary unicyclic graph, where k is the length of the cycle. In the last section we give tight lower and upper bounds on broadcast time of a spanning tree based on the broadcast time of the unicyclic graph. The results of Sects. 2, 3 and most of the proofs in Sects. 2, 3 of this paper are presented by Harutyunyan and Maraachlian (Proceedings of 13th annual COCOON, pp. 372–383, 2007). All results in Sects. 4, 5 and the complete proof of Theorem 3 are new results.     

Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis

We study group-testing algorithms for resolving broadcast conflicts on a multiple access channel (MAC) and for identifying the dead sensors in a mobile ad hoc wireless network. In group-testing algorithms, we are asked to identify all the defective items in a set of items when we can test arbitrary subsets of items. In the standard group-testing problem, the result of a test is binary—the tested subset either contains defective items or not. In the more generalized versions we study in this paper, the result of each test is non-binary. For example, it may indicate whether the number of defective items contained in the tested subset is zero, one, or at least two. We give adaptive algorithms that are provably more efficient than previous group testing algorithms. We also show how our algorithms can be applied to solve conflict resolution on a MAC and dead sensor diagnosis. Dead sensor diagnosis poses an interesting challenge compared to MAC resolution, because dead sensors are not locally detectable, nor are they themselves active participants. A preliminary version of this paper was presented at SPAA 2006.     

New combinatorial structures with applications to efficient group testing with inhibitors

Group testing with inhibitors (GTI) is a variant of classical group testing where in addition to positive items and negative items, there is a third class of items called inhibitors. In this model the response to a test is YES if and only if the tested group of items contains at least one positive item and no inhibitor. This model of group testing has been introduced by Farach et al. (Proceedings of compression and complexity of sequences, pp 357–367, 1997) for applications in the field of molecular biology. In this paper we investigate the GTI problem both in the case when the exact number of positive items is given, and in the case when the number of positives is not given but we are provided with an upper bound on it. For the latter case, we present a lower bound on the number of tests required to determine the positive items in a completely nonadaptive fashion. Also under the same hypothesis, we derive an improved lower bound on the number of tests required by any algorithm (using any number of stages) for the GTI problem. As far as it concerns the case when the exact number of positives is known, we give an efficient trivial two-stage algorithm. Instrumental to our results are new combinatorial structures introduced in this paper. In particular we introduce generalized versions of the well known superimposed codes (Du, D.Z., Hwang, F.K. in Pooling designs and nonadaptive group testing, 2006; Dyachkov, A.G., Rykov, V.V. in Probl. Control Inf. Theory 12:7–13, 1983; Dyachkov, A.G., et al. in J. Comb. Theory Ser. A 99:195–218, 2002; Kautz, W.H., Singleton, R.R. in IEEE Trans. Inf. Theory 10:363–377, 1964) and selectors (Clementi, A.E.F, et al. in Proceedings of symposium on discrete algorithms, pp. 709–718, 2001; De Bonis, A., et al. in SIAM J Comput. 34(5):1253–1270, 2005; Indyk, P. in Proceedings of symposium on discrete algorithms, pp. 697–704, 2002) that we believe to be of independent interest.     

非正式组织演进路径实证研究

本文基于组织行为学视角,以天津市部分企业员工为调查对象,通过问卷调查和调查访谈,对企业非正式组织演进路径进行了实证研究。研究发现,非正式组织与组织成员心理特征、非正式组织领袖、企业文化及其结构特征具有相关性。本文还辩析了非正式组织演进路径模型,并在此基础上,得出管理非正式组织的启示。     

On the upper total domination number of Cartesian products of graphs

In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning, M.A., Rall, D.F. in Graphs Comb. 21:63–69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ _t (G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, Γ _t (G)Γ _t (H)≤2Γ _t (G □ H). Research of M.A. Henning supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

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.     

基于DEA的战略组识别

战略组分析是产业组织理论与战略管理理论中的重要分析工具。但战略组的概念模糊性和战略维度和变量选择以及聚类方法的主观性,使得关于战略组识别存在着矛盾的结论。DEA是适合于明确战略组概念和识别战略组的方法。修正后的DEA,如DEA-Window,特别是最优权多重性问题的解决,能较好地识别战略组。     

A hard clustering approach to the part family formation problem

The part family problem in group technology can be stated as the problem of finding the best grouping of parts into families such that the parts within each family are as similar to each other as possible. In this paper, the part family formation problem is considered. The problem is cast into a hard clustering model, and the k-means algorithm is proposed for solving it. Preliminary computational experience on the algorithm is very encouraging and it shows that real-life problems of large sizes can efficiently be handled by this approach.     

Dynamic Group Scheduling Heuristics in a Flow-through Cell Environment*

The increased use of cellular manufacturing configurations designed to grapple with increasing competitive pressures is providing manufacturing managers and engineers with a broad variety of operational challenges. Many questions concerning the best procedures and policies for the day-to-day operation of manufacturing cells are still unanswered. The primary objective of this study is to compare the performance of traditional single-stage heuristics and the two-stage group scheduling heuristics that have exhibited superior performance in previous studies in a flow-through cell environment under a rigorous set of experimental conditions. Such a comparison is of great interest since each previous study has focused on proposing new heuristics and testing them against some particular baseline heuristic, often without comprehensive comparisons to the broad variety of previously proposed heuristics. Two single-stage heuristics and four two-stage heuristics are examined under sixteen experimental conditions (four experimental factors at two levels each). The experimental factors examined are shop load, due date tightness, setup to run-time ratio, and interarrival time distribution. Results vary by experimental condition and performance criteria, but in general, two-stage heuristics outperformed single-stage heuristics under all experimental conditions, as well as being relatively insensitive to changing experimental conditions. In addition, two of the two-stage heuristics displayed superior performance on all performance measures under most experimental conditions. Finally, the results indicated that interarrival time distribution does have a major impact on the performance of scheduling heuristics.     

Formalized Dissent and Cognitive Complexity in Group Processes and Performance*

Research suggests that two methods of introducing dissent, the dialectic inquiry (DI) and devil's advocate (DA) methods, show promise for increasing the cognitive complexity of decision makers. We investigated the joint effects of formalized dissent and group cognitive complexity by manipulating the formalized dissent method (DI or DA) used by 25 interacting groups engaged in a complex, ill-structured planning task. Participants were classified as either high or low cognitive complexity and assigned to stratified groups with members of homogeneous complexity. Results indicated that: (1) DA groups produced higher quality assumptions but took longer to generate plans than did DI groups, (2) high complexity groups generated more recommendations relative to low complexity groups, and (3) DA groups with low complexity members produced lower quality recommendations and participated less equally in decision making than did the other groups. We conclude by discussing the implications of the results for formalized dissent, cognitive complexity, and assessing managerial performance.     

一种基于偏好分布的群决策方法

为了满足群决策的实际需求,本文提出了一种基于偏好分布的群决策方法,该方法利用完全不对称预先排序向量表示决策者的偏好,通过分析计算偏好排序向量的密度和分布结构,从可行方案集合中寻找所有决策者都能接受的优选方案集合,逐次缩小搜索空间以逼近一致满意解。该方法结合冲突分析,可进一步分析决策者之间的相互关系,集成于谈判支持系统,具有直观、实用等特点,最后给出了一个实际例子说明该方法。