Additive manufacturing is a multi-billion dollar industry 21.58 billion in 2024), so its processes should be dependable and secure. Malicious actors can inject negative spaces, known as voids, in STL files, which can have a devastating impact on a final product's quality. Current ways of detecting voids use machine sensor or simulation data, and physical verification measures after printing. However, to the best of our knowledge, no method exists for detecting hidden voids solely at the STL level. Void detection at this level is inexpensive, and has the potential to detect voids in designs en masse. In this work, we proposeAVOID, a new approach to detect hidden voids. It both detects voids, and assesses their risk of weakening the manufactured part.AVOIDperforms risk assessment based on the size and location of each detected void. We empirically evaluatedAVOIDusing several large datasets, in total thousands of STL files, each with multiple hidden voids. We found thatAVOIDis highly accurate, with 97.7% recall, 98.1% precision, and 99% F1 on average across six data sets.AVOIDis also robust, scalable, and efficient. We find that high risk voids account for approximately 7% of all detected voids inserted randomly.

In this paper, we introduce a novel optical communication paradigm that uses femtosecond mode-locked lasers carrier wave and spatial light modulators for communication. Our paradigm leverages properties of femtosecond lasers for high speed and secure data transmission. While previous literature has explored the potential of femtosecond lasers, little research has focused on developing communication based on this technology especially the carrier envelope phase inherent to a femtosecond laser pulse. To validate the feasibility of our new paradigm we perform simulations investigating the impact of spectrum manipulation on ultrashort pulses. We also study dispersion assessment of the carrier envelope phase of ultrashort lasers. The understanding of carrier envelope phase shift contributes to the development of compensation method, and also enhance network security. We use the simulation to assess the behavior of ultrashort lasers to detect the tampering of the transmission medium. It is important to point out that it is only recently that carrier envelope locked lasers have been demonstrated experimentally at a few laboratories. Our paradigm is motivated by finding a solution to the capacity limitations of optical communications and introduces a new layer of security. It holds significant potential for high-speed data networks, secure communication, and the future of communication infrastructure.

MOTIVATION: Encoded by (pro-)viruses, anti-CRISPR (Acr) proteins inhibit the CRISPR-Cas immune system of their prokaryotic hosts. As a result, Acr proteins can be employed to develop more controllable CRISPR-Cas genome editing tools. Recent studies revealed that known acr genes often coexist with other acr genes and with phage structural genes within the same operon. For example, we found that 47 of 98 known acr genes (or their homologs) co-exist in the same operons. None of the current Acr prediction tools have considered this important genomic context feature. We have developed a new software tool AOminer to facilitate the improved discovery of new Acrs by fully exploiting the genomic context of known acr genes and their homologs. RESULTS: AOminer is the first machine learning based tool focused on the discovery of Acr operons (AOs). A two-state HMM (hidden Markov model) was trained to learn the conserved genomic context of operons that contain known acr genes or their homologs, and the learnt features could distinguish AOs and non-AOs. AOminer allows automated mining for potential AOs from query genomes or operons. AOminer outperformed all existing Acr prediction tools with an accuracy = 0.85. AOminer will facilitate the discovery of novel anti-CRISPR operons. AVAILABILITY AND IMPLEMENTATION: The webserver is available at: http://aca.unl.edu/AOminer/AOminer_APP/. The python program is at: https://github.com/boweny920/AOminer.

Network Function Virtualization (NFV) replaces physical middleboxes with elastic Virtual Network Functions (VNFs). Those VNFs need to be instantiated, and their resources dynamically scaled to meet application and traffic fluctuation requirements. Despite recent extensive research, deciding how to map virtual resources optimally to the underlying infrastructure remains practically a challenge. Existing approaches mostly assign fixed resources to each VNF instance, and transfer virtual flows using a single physical path, without prior knowledge of traffic patterns and available bandwidth. Such resource binding strategies lead to suboptimal physical link utilization. We advance the state of the art in this regard by presenting OctoMap, a system designed to support with learning theory any chain embedding algorithm. OctoMap utilizes a Convolution Neural Network for traffic prediction and provisioning, and a contextual multi-armed bandit algorithm to solve the online VNF chain embedding problem. We show the performance benefits of OctoMap with a trace-driven simulation campaign using publicly available datasets. In particular, we show how OctoMap reduces the costs of provisioning network services under node and link constraints, comparing different predictors and different multi-armed bandit policies.

BACKGROUND: Systems-level analyses, such as differential gene expression analysis, co-expression analysis, and metabolic pathway reconstruction, depend on the accuracy of the transcriptome. Multiple tools exist to perform transcriptome assembly from RNAseq data. However, assembling high quality transcriptomes is still not a trivial problem. This is especially the case for non-model organisms where adequate reference genomes are often not available. Different methods produce different transcriptome models and there is no easy way to determine which are more accurate. Furthermore, having alternative-splicing events exacerbates such difficult assembly problems. While benchmarking transcriptome assemblies is critical, this is also not trivial due to the general lack of true reference transcriptomes. RESULTS: In this study, we first provide a pipeline to generate a set of the simulated benchmark transcriptome and corresponding RNAseq data. Using the simulated benchmarking datasets, we compared the performance of various transcriptome assembly approaches including both de novo and genome-guided methods. The results showed that the assembly performance deteriorates significantly when alternative transcripts (isoforms) exist or for genome-guided methods when the reference is not available from the same genome. To improve the transcriptome assembly performance, leveraging the overlapping predictions between different assemblies, we present a new consensus-based ensemble transcriptome assembly approach, ConSemble. CONCLUSIONS: Without using a reference genome, ConSemble using four de novo assemblers achieved an accuracy up to twice as high as any de novo assemblers we compared. When a reference genome is available, ConSemble using four genome-guided assemblies removed many incorrectly assembled contigs with minimal impact on correctly assembled contigs, achieving higher precision and accuracy than individual genome-guided methods. Furthermore, ConSemble using de novo assemblers matched or exceeded the best performing genome-guided assemblers even when the transcriptomes included isoforms. We thus demonstrated that the ConSemble consensus strategy both for de novo and genome-guided assemblers can improve transcriptome assembly. The RNAseq simulation pipeline, the benchmark transcriptome datasets, and the script to perform the ConSemble assembly are all freely available from: http://bioinfolab.unl.edu/emlab/consemble/ .

Multi-homed mobile devices are capable of aggregating traffic transmissions over heterogeneous networks. MultiPath TCP (MPTCP) is an evolution of TCP that allows the simultaneous use of multiple interfaces for a single connection. Despite the success of MPTCP, its deployment can be enhanced by controlling which network interface to be used as an initial path during the connectivity setup. In this paper, we proposed an online MPTCP path manager based on the contextual bandit algorithm to help choose the optimal primary path connection that maximizes throughput and minimizes delay and packet loss. The contextual bandit path manager deals with the rapid changes of multiple transmission paths in heterogeneous networks. The output of this algorithm introduces an adaptive policy to the path manager whenever the MPTCP connection is attempted based on the last hop wireless signals characteristics. Our experiments run over a real dataset of WiFi/LTE networks using NS3 implementation of MPTCP, enhanced to better support MPTCP path management control. We analyzed MPTCP's throughput and latency metrics in various network conditions and found that the performance of the contextual bandit MPTCP path manager improved compared to the baselines used in our evaluation experiments. Utilizing edge computing technology, this model can be implemented in a mobile edge computing server to dodge MPTCP path management issues by communicating to the mobile equipment the best path for the given radio conditions. Our evaluation demonstrates that leveraging adaptive context-awareness improves the utilization of multiple network interfaces.

Identification of the conserved non-coding sequences (CNSs) for plants is a challenging problem because the plants have small CNSs compared to animals. The existing alignment based methods are neither efficient nor sensitive to smaller CNSs when the number of species is large. In this paper, we propose an alignment-free approach that can process any number sequences simultaneously. Our approach uses maximal repeats extracted from generalized suffix tree of the sequences and discovers both exactly matched CNSs as well as CNSs with a given mismatch rate. The experimental results with 17, 996 syntenic genes of six grass species shows that our approach is more efficient than existing approaches.

Accurate transcriptome assembly using next-generation sequencing data is crucial in gene expression analysis. However, it has been observed that different assemblers generate significantly different outputs given the same RNA-Seq data. Even the same method often assembles different sets of transcripts when different sets of parameters are used. In this study, we performed comparative analysis of various transcriptome assemblers including four de novo and three genome-guided methods using simulated RNA-Seq data modeling Illumina Hi-Seq sequencing of Arabidopsis thaliana and Zea mays strain B73 transcriptomes. No assembler was able to reconstruct all of the reference transcripts correctly. A large number (~30%) of transcripts were not assembled correctly by any assembler. Furthermore, each assembler produced a different set of reference transcripts with very few that are common among all. While the de novo tools were able to assemble similar numbers of transcripts correctly as genome-guided tools for one dataset, the former methods also produced much larger numbers of incorrectly assembled transcripts compared to genome-guided tools. These results indicate that there remains a large room for transcriptome assembly to be improved. Therefore, we further investigated a consensus-based ensemble approach. By taking the consensus contig set shared, for example, among three or more de novo assemblers, 10% more transcripts were correctly identified for Arabidopsis thaliana datasets. While the incorrect to correct contig ratio for the de novo assemblers ranged from 4.9 (for Trinity) to 10.7 (SOAPdenovo), for the genome-guided methods the ratios were from 1.3 to 1.7. Using the consensus de novo method, we successfully reduced the ratio to the level very close to or even lower than those obtained by the genome-guided methods (1.5). The results of this study provides us a direction to build a better ensemble approach that can reconstruct all the correct transcripts.

Alignment of sequence reads is an important step of many bioinformatics workflows. While the alignment of short reads is well investigated, the alignment of long reads produced by third-generation sequencing technologies, such as Oxford Nanopore, is more challenging because they have high error rates (10-40%). Furthermore, due to their different algorithmic approaches, different tools produce varied alignments, significantly influencing the downstream analyses. In this study, we evaluated the performance of three alignment tools (LAST, GraphMap, and NanoBLASTer) using simulated nanopore reads. Although the three alignment strategies gave similar results (e.g., all close to 100% precision), GraphMap reported the longest alignments while LAST the shortest. However, GraphMap showed the lowest recall (90%) indicating high false negative rates. While GraphMap had the highest percentage of reads that were mapped to the correct reference regions, NanoBLASTer and especially LAST mapped the majority of the reads only partially correctly. Based on our multiple statistics, GraphMap had the best overall performance.

In this paper, we propose OWCells, a class of optical wireless cellular data center network architectures in which fixed line of sight (LOS) optical wireless communication (OWC) links are used to connect racks of servers arranged in regular polygonal topologies. We present the OWCell DCN architecture, develop its theoretical underpinnings, and investigate routing protocol and OWC transceiver design. Simulations are conducted to validate and compare the performance of OWCell. The impact of OWCell design parameters on its performance is also investigated. We compare the performance of OWCell using OCS and hybrid (OCS+OBS) switching schemes. The performance of OWCell is comparatively evaluated with HyScale DCN, a switch-centric hybrid optical DCN. Simulation results show that OWCell can reduce the number of links up by 95-98% while maintaining a performance that is within 15-25% that of HyScale. We discuss future research directions and approaches to improve the performance of the proposed OWCell DCN architectures.

Cognitive cellular networks can enable opportunistic network access but their effectiveness relies on adaptive handoff algorithms. However, in cognitive radio networks the usufructuary rights of a secondary user are rescinded due to the unanticipated appearance of a primary user causing potential service disruption. In order to provide uninterrupted service to a cognitive cellular user, we propose elastic handoff as a composite framework of conventional cellular and voluntary spectrum handoffs. As with spectrum handoff, elastic handoff grants secondary users spectrum access while insulating them against the arrival of primary users. On the other hand, it is similar to cellular handoff in providing secondary users service assurance. The setup also offers users multiple network access choices, and affords carriers the means to generate additional revenue by capitalizing on excess capacity. We use a blockchain-based spectrum exchange and smart contracts to implement elastic handoff. Our tests show that user-initiated elastic handoff may reduce call drops by up to half compared to observations from a conventional cellular market, and network-initiated elastic handoff can improve a carrier's revenue maximization prospects.

Cloud-centric cognitive cellular networks utilize dynamic spectrum access and opportunistic network access technologies as a means to mitigate spectrum crunch and network demand. However, furnishing a carrier with personally identifiable information for user setup increases the risk of profiling in cognitive cellular networks, wherein users seek secondary access at various times with multiple carriers. Moreover, network access provisioning - assertion, authentication, authorization, and accounting - implemented in conventional cellular networks is inadequate in the cognitive space, as it is neither spontaneous nor scalable. In this paper, we propose a privacy-enhancing user identity management system using blockchain technology which places due importance on both anonymity and attribution, and supports end-to-end management from user assertion to usage billing. The setup enables network access using pseudonymous identities, hindering the reconstruction of a subscriber's identity. Our test results indicate that this approach diminishes access provisioning duration by up to 4x, decreases network signaling traffic by almost 40%, and enables near real-time user billing that may lead to approximately 3x reduction in payments settlement time.

With advances in next-generation sequencing technologies, transcriptome sequencing has emerged as a powerful tool for performing transcriptome analysis for various organisms. Obtaining draft transcriptome of an organism is a complex multi-stage pipeline with several steps such as data cleaning, error correction and assembly. Based on the analysis performed in this paper, we conclude that the best assembly is produced when the error correction method is used with Velvet Oases and the “multi-k” strategy that combines the 5 k-mer assemblies with highest N50. Our results provide valuable insight for designing good de novo transcriptome assembly pipeline for a given application.

The growing density of cellular users is placing an unprecedented demand on radio spectrum. Cognitive cellular networks can alleviate spectrum demand through dynamic spectrum access. In order to be fully functional, cellular users not only need spectrum access but also require network access. However, a cellular carrier grants network access only to accredited users. In this paper, we focus on the problem of opportunistic network access for unaccredited users by spontaneous provisioning in the context of cognitive cellular networks. We achieve this for both single and group users by extending the traditional 3A security framework - authentication, authorization, and accounting - to a 5A security paradigm. This entails the addition of network access and user assertion. We design several simulations based on a proof-of-principle prototype to validate our approach against multiple traffic models. The results show our approach can deliver at least 13% improvement in user provisioning time compared to conventional schemes.

In this paper, we propose an N × N rearrangeable nonblocking (RNB) multicast free space optical (FSO) switch using non-movable tri-state switching elements (T-SEs). The proposed switch exhibits an optimal hardware complexity as it requires only N(N +1)/2 switching elements. The switch is analyzed and compared to existing optical multicast switches in terms of hardware complexity, power loss, and cost. Comparison results show that the proposed switch provides multicast capability with a lower hardware complexity and a comparable performance. Cost analysis shows that, for N = 4, the overall cost of the new design is lower than that of existing SNB switches even if the T-SE is 4 to 10 times the cost of typical MEMS mirrors. In addition, we present a simple routing algorithm that systematically establishes connections over the new switch.

In this paper, we propose a novel design of a data center (DC) using free space optical (FSO) technology. The proposed FSO-DC design is based on fixed, non-mechanical, FSO links facilitating the realization of fully connected FSO racks and rows/columns of racks. Each rack becomes a point of intersection of three fully connected sub-networks. We investigate requirements, advantages and challenges of the proposed design. We develop and analyze a switch-free, fully connected FSO rack, present its link budget analysis and validate it by simulation. Results establish the feasibility of a switch-free FSO rack based on the proposed FSO-DC design. A cost estimate for the proposed FSO-DC design is also presented and compared to three well-known conventional DC designs.

Next-generation multiprocessor real-time systems consume less energy at the cost of increased power density. This increase in power density results in high heat density and may affect the reliability and performance of real-time systems. Thus, incorporating maximum temperature constraints in scheduling of real-time task sets is an important challenge. This paper investigates a novel algorithm for thermal-constrained energy-aware partitioning of periodic real-time tasks in heterogeneous multiprocessor systems. When designing our new algorithm, we have applied insights gained from a famous knapsack problem solution. Both simulation and experimental results show that our new branch-and-bound based partitioning algorithm can significantly reduce the total energy consumption of multiprocessor real-time systems.

BACKGROUND: Our environment is composed of biological components of varying magnitude. The relationships between the different biological elements can be represented as a biological network. The process of mating in S. cerevisiae is initiated by secretion of pheromone by one of the cells. Our interest lies in one particular question: how does a cell dynamically adapt the pathway to continue mating under severe environmental changes or under mutation (which might result in the loss of functionality of some proteins known to participate in the pheromone pathway). Our work attempts to answer this question. To achieve this, we first propose a model to simulate the pheromone pathway using Petri nets. Petri nets are directed graphs that can be used for describing and modeling systems characterized as concurrent, asynchronous, distributed, parallel, non-deterministic, and/or stochastic. We then analyze our Petri net-based model of the pathway to investigate the following: 1) Given the model of the pheromone response pathway, under what conditions does the cell respond positively, i.e., mate? 2) What kinds of perturbations in the cell would result in changing a negative response to a positive one? METHOD: In our model, we classify proteins into two categories: core component proteins (set ψ) and additional proteins (set λ). We randomly generate our model's parameters in repeated simulations. To simulate the pathway, we carry out three different experiments. In the experiments, we simply change the concentration of the additional proteins (λ) available to the cell. The concentration of proteins in ψ is varied consistently from 300 to 400. In Experiment 1, the range of values for λ is set to be 100 to 150. In Experiment 2, it is set to be 151 to 200. In Experiment 3, the set λ is further split into σ and ς, with the idea that proteins in σ are more important than those in ς. The range of values for σ is set to be between 151 to 200 while that of ς is 100 to 150. Decision trees were derived from each of the first two experiments to allow us to more easily analyze the conditions under which the pheromone is expressed. CONCLUSION: The simulation results reveal that a cell can overcome the detrimental effects of the conditions by using more concentration of additional proteins in λ. The first two experiments provide evidence that employing more concentration of proteins might be one of the ways that the cell uses to adapt itself in inhibiting conditions to facilitate mating. The results of the third experiment reveal that in some case the protein set σ is sufficient in regulating the response of the cell. Results of Experiments 4 and 5 reveal that there are certain conditions (parameters) in the model that are more important in determining whether a cell will respond positively or not.

The Internet has recently been evolving from homogeneous congestion control to heterogeneous congestion control. Several years ago, Internet traffic was mainly controlled by the traditional RENO, whereas it is now controlled by multiple different TCP algorithms, such as RENO, CUBIC, and Compound TCP (CTCP). However, there is very little work on the performance and stability study of the Internet with heterogeneous congestion control. One fundamental reason is the lack of the deployment information of different TCP algorithms. In this paper, we first propose a tool called TCP Congestion Avoidance Algorithm Identification (CAAI) for actively identifying the TCP algorithm of a remote Web server. CAAI can identify all default TCP algorithms (e.g., RENO, CUBIC, and CTCP) and most non-default TCP algorithms of major operating system families. We then present the CAAI measurement result of about 30 000 Web servers. We found that only 3.31 % ~ 14.47 % of the Web servers still use RENO, 46.92% of the Web servers use BIC or CUBIC, and 14.5 % ~ 25.66 % of the Web servers use CTCP. Our measurement results show a strong sign that the majority of TCP flows are not controlled by RENO anymore, and a strong sign that the Internet congestion control has changed from homogeneous to heterogeneous.

Energy consumption is becoming a serious issue for data centers. Minimizing the energy consumption of a data center is a complex problem. It consists of developing energy models for servers and network elements and investigating energy-aware (green) routing strategies using these models. In this paper, we adapt energy models for servers and network elements in a data center. The server energy model incorporates the impact of temperature and voltage of a server on its leakage energy. Using the server and network energy models, we propose a green routing scheme that minimizes the total combined energy consumption of servers and network elements in a data center under dynamic traffic. The proposed green routing scheme uses dynamic voltage scaling, rate adaptation, and anycast transmission for minimizing the total energy consumption. Extensive simulation results validate the effectiveness of the proposed green routing in minimizing the total energy consumption of a data center as compared to well-known existing approaches.

Data Center Network architectures (DCN) are evolving for increased scalability, performance, and low network complexity. In this paper, we propose HyScale, a switch-centric DCN architecture using hybrid optical networks. HyScale employs Optical Burst Switching and Optical Circuit Switching technologies for transmitting low and high volumes of data respectively in a data center. The proposed architecture is highly scalable, recursively defined, fault-tolerant, and has low network complexity. It also has a multitude of desirable graph-theoretic properties like high bisection width, and low diameter. By exploiting the structural properties of HyScale, we propose a highly efficient and simple routing scheme. In our experiments, the proposed routing scheme gives a lower packet loss ratio by an average of 23% as compared to the Shortest Path Routing with almost negligible increase in the length of the routes.

Next-generation multi-core multiprocessor real-time systems consume less energy at the cost of increased power density. This increase in power-density results in high heat density and may affect the reliability and performance of real-time systems. Thus, incorporating maximum temperature constraints in scheduling of real-time task sets is an important challenge. This paper investigates thermal-constrained energy-aware partitioning of periodic real-time tasks in heterogeneous multi-core multiprocessor systems. We adopt a power model which considers the impact of temperature and voltage on a processor's static power consumption. Two types of thermal models are used to respectively capture negligible and non-negligible amount of heat transfer among cores. We develop a novel genetic-algorithm based approach to solve the heterogeneous multi-core multiprocessor partitioning problem. Extensive simulations were performed to validate the effectiveness of the approach. Experimental results show that integrating a worst-fit based partitioning heuristic with the genetic algorithm can significantly reduce the total energy consumption of a heterogeneous multi-core multiprocessor real-time system.

Software Product Line Engineering (PLE) exploits systematic reuse by identifying and methodically reusing software artifacts to develop different but related software systems. Developing Product Lines requires analysis skills to identify, model, and encode domain and product knowledge into artifacts that can be systematically reused across the development life-cycle. As such, Knowledge plays a paramount role in the success of the various activities of PLE. The objective of the KOPLE workshop series is to bring together SPL researchers and practitioners from academia and industry to investigate the role of Knowledge in PLE. Knowledge is usually encapsulated in PL architectures in a tacit or implicit way, and this may appear to be sufficient for industry to implement successful product lines. Nevertheless, KOPLE also aims to become a discussion forum about techniques and methods to convert from tacit to explicit Knowledge in PLE and to process and use this Knowledge for optimizing and innovating PLE processes.

The state of the resources at a destination in Grid computing over OBS architecture (GoOBS) may change between a task's selection of a destination and its arrival at the destination. These changes in the availability of the resources requested at the destination may lead to blocking of tasks, and thus increase the resource blocking rate. In this paper, we investigate the resource scheduling problem in GoOBS. Our objective is to minimize the resource blocking rate by containing the impact of the changes in the availability of the resources at a destination. We propose a non-selfish destination selection paradigm to minimize the resource blocking rate. The selection of a destination by a request is called non-selfish, if the selected destination has sufficient resources available to simultaneously process one or more additional requests. Extensive simulations were performed to validate the effectiveness of the heuristics based on the non-selfish destination selection paradigm. Among the proposed heuristics, the NFFD heuristic is most effective in minimizing the resource blocking rate. Compared to the best existing approach, the NFFD heuristic reduces the resource blocking rate by 21% to 73% in our experiments.

The Internet has recently been evolving from homogeneous congestion control to heterogeneous congestion control. Several years ago, Internet traffic was mainly controlled by the traditional AIMD algorithm, whereas Internet traffic is now controlled by many different TCP algorithms, such as AIMD, BIC, CUBIC, and CTCP. However, there is very little work on the performance and stability study of the Internet with heterogeneous congestion control. One fundamental reason is the lack of the deployment information of different TCP algorithms. In this paper, we first propose a tool called TCP Congestion Avoidance Algorithm Identification (CAAI) for actively identifying the TCP algorithm of a remote web server. CAAI can identify all default TCP algorithms (i.e., AIMD, BIC, CUBIC, and CTCP) and most non-default TCP algorithms of major operating system families. We then present, for the first time, the CAAI measurement result of the 5000 most popular web servers. Among the web servers with valid traces, we found that only 16.85~25.58\% of web servers still use the traditional AIMD, 44.51\% of web servers use BIC or CUBIC, and 10.27$\sim$19\% of web servers use CTCP. In addition, we found that, for the first time, some web servers use non-default TCP algorithms, some web servers use some unknown TCP algorithms which are not available in any major operating system family, and some web servers use abnormal slow start algorithms. Our CAAI measurement results show a strong sign that the majority of TCP flows are not controlled by AIMD anymore, and a strong sign that the Internet congestion control has already changed from homogeneous to highly heterogeneous.

Providing QoS and performance guarantees to arbitrarily divisible loads has become a significant problem for many cluster-based research computing facilities. While progress is being made in scheduling arbitrarily divisible loads, current approaches are not efficient and do not scale well. In this paper, we propose a linear algorithm for real-time divisible load scheduling. Unlike existing approaches, the new algorithm relaxes the tight coupling between the task admission controller and the task dispatcher. By eliminating the need to generate exact schedules in the admission controller, the algorithm avoids high overhead. We experimentally evaluate the new algorithm. Simulation results demonstrate that the algorithm scales well, can schedule large numbers of tasks efficiently, and performs similarly to existing approaches in terms of providing real-time guarantees.

For decades, US universities and colleges have had policies pertaining to the conduct of their students at the institutional level. These policies are referred to as Academic Integrity Policies or Codes of Conduct. The Code of Ethics, instituted by Association of Computing Machinery (ACM) has been the standard for the computing sciences profession for over 15 years. However, the traditional institution-wide academic integrity policies have not adapted to the complexities that arose from rapid progress in information technology (IT) and thus either fail to address or are in conflict with the nature of problems in computer science education. In this paper, we propose a model for development and implementation of an academic ethics policy (ethics is a broader concept that includes integrity) that addresses the challenges imposed by information technology vis-a-vis the best modern teaching practices in computer sciences and engineering. Implementing policies that are more in line with the methods of industry and compatible with newer educational pedagogies should make the whole educational environment more engaging to students.

The network coding paradigm has become an effective method for achieving efficient multicast in communication networks. The optical community has just started to venture into the application of network coding in optical networks. However, a number of challenges need to be overcome before network coding can be used in optical networks. These include limited buffering and processing capabilities as well as extremely coarse bandwidth granularity. In this paper, we address some of these problems. Finding multicast codes can be broken into two subproblems: finding a subgraph of the topology to code over and then finding an actual code for that subgraph. We show that the former problem is NP-Complete and provide heuristics which allow for coded multicast in optical wavelength division multiplexing networks which offer a modest improvement in bandwidth efficiency over traditional methods for finding routes for optical-layer multicast traffic.

Providing QoS and performance guarantees to arbitrarily divisible loads has become a significant problem for many cluster-based research computing facilities. While progress is being made in scheduling arbitrarily divisible loads, previous approaches have no support for advance reservations. However, with the emergence of grid applications that require simultaneous access to multi-site resources, supporting advance reservations in a cluster has become increasingly important. In this paper we propose a new divisible load real-time scheduling algorithm that supports advance reservations in a cluster. Our approach not only enforces the real-time agreement but also addresses the under-utilization concerns raised by advance reservations. The impact of advance reservations on system performance is systematically studied. Simulation results show that, with the proposed algorithm and appropriate advance reservations, the system performance could be maintained at the same level as the no reservation case.

In this paper, a new design for strictly nonblocking WDM networks with full permutation and multicast switching capability is proposed. In the proposed design, we use space concentrators to reduce the switching complexity and multi-wavelength converters to reduce the cost of wavelength conversion in the network. A multi-wavelength converter is capable of simultaneously replicating a signal on an input wavelength to several different output wavelengths. The proposed approach provides a versatile framework for designing multicast switching networks with many a different tradeoffs between switching and conversion complexities to meet variety of application needs and technology constraints. A comparative analysis of the proposed multicast switching network and the existing design is also presented.

Recent advances in radio frequency identification (RFID) technology are leading to promising means for significant enhancement of safety, quality and value of health care. In this paper, we give an overview of the state-of-art research in applications of RFID in hospitals. We outline the challenges in designing RFID based systems for hospitals, and point out open problems and future research directions.

Recently, the use of pre-crossconnected trails (PXTs) has been proposed for fault tolerant WDM optical networks. Arranging protection bandwidth into PXTs eliminates the need for switch reconfiguration after a failure which leads to faster recovery times. The researchers who introduced PXTs gave experimental results showing that PXT protection performs not much worse and sometimes better than conventional algorithms in terms of bandwidth efficiency. Their experiments compared a greedy PXT algorithm with a simple non-greedy conventional algorithm, so there remained some question about the effect of the PXT constraint itself on bandwidth efficiency. In this paper, we explore this topic further. We use experimental results to compare simple and greedy heuristics both with and without the PXT constraint. Our results show that the PXT variations require significantly more bandwidth overhead than their conventional counterparts especially in larger networks.

Providing QoS and performance guarantees to arbitrarily divisible loads has become a significant problem for many cluster-based research computing facilities. While progress is being made in scheduling arbitrarily divisible loads, some of proposed approaches may cause inserted idle times (IITs) that are detrimental to system performance. In this paper we propose a new approach that utilizes IITs and thus enhances the system performance. The novelty of our approach is that, to simplify the analysis, a homogenous system with IITs is transformed to an equivalent heterogeneous system, and that our algorithms can schedule real-time divisible loads with different processor available times. Intensive simulations show that the new approach outperforms the previous approach in all configurations. We also compare the performance of our algorithm to the current practice of manually splitting workloads by users. Simulation results validate the advantages of our approach.

Cluster computing has emerged as a new paradigm for solving large-scale problems. To enhance QoS and provide performance guarantees in cluster computing environments, various real-time scheduling algorithms and workload models have been investigated. Computational loads that can be arbitrarily divided into independent pieces represent many real-world applications. Divisible load theory (DLT) provides insight into distribution strategies for such computations. However, the problem of providing performance guarantees to divisible load applications has not yet been systematically studied. This paper investigates such algorithms for a cluster environment. Design parameters that affect the performance of these algorithms and scenarios when the choice of these parameters have significant effects are studied. A novel algorithmic approach integrating DLT and EDF (earliest deadline first) scheduling is proposed. For comparison, we also propose a heuristic algorithm. Intensive experimental results show that the application of DLT to real-time cluster-based scheduling leads to significantly better scheduling approaches

In this paper, we develop a new class of three-stage Clos-like wavelength division multiplexing (WDM) optical interconnects with reduced hardware cost and control complexity. A novel WDM crossbar switch is developed and is used as a building block for designing the proposed class of WDM interconnects. We parameterize the design space and give a complete characterization of the proposed class. Our analysis of the hardware design complexity shows that the proposed design compares favorably to most existing WDM interconnects. We also show that the proposed crossbar switch and the new class of WDM interconnects admit most existing routing algorithms with simple extensions.

Classifying G protein-coupled receptors (GPCRs) is an interesting topic because of the important role of GPCRs in pharmaceutical research. GPCRs have diverse functions and are involved in many biological processes, which makes them an ideal target of novel medicine. The diverse nature of GPCRs results in the lack of overall sequence homolog among the members, making the classification of GPCRs a very challenging task. Various approaches and methods have been applied to this task, such as HMM, decision tree, and SVM. However, their performances are not completely satisfactory. In this paper, we propose a new method to classify GPCRs into different subfamilies. In the proposed method, the probabilistic suffix tree (PST) is used to construct a prediction model for each of the subfamilies. To classify a GPCR protein, we calculate its similarity score against the PST prediction model of each subfamily using the multi-domain local prediction algorithm. The protein is then classified into the subfamily which gives it the highest score. Our method only uses the primary sequence information and is also very efficient. The model construction and prediction process takes very short time. However, it reports the 98.07% and 97.35% overall accuracy on the level I and II subfamily classification in a 2-fold cross validation test respectively. Given the high accuracy and efficiency, our method is a significant improvement on previously reported ones

In this paper, we propose a new optical path cross connect (OXC) architecture for wavelength division multiplexing (WDM) networks with reduced switching and conversion complexity. The proposed OXC is based on two design principles: bulk wavelength conversion, and single-step space/wavelength switching. Combined power of these two design principles lead to a novel OXC design with minimum number of switches as well as wavelength conversions. The proposed design follows the structure of the well-known Benes network and provides a full-permutation connectivity in both space and wavelength domains using only 2 log2N - 2 switching stages, and thus, requires N/2 less switching elements (N = FW, where F is the total number of fibers and W that of wavelengths). We investigate the main properties of the proposed design and compare it to well-known existing OXCs.

In this paper, we present a new design approach for WDM optical interconnects that reduces both switching and wavelength conversion complexity. The proposed design approach employs wavelength conversion strictly between two pre-specified wavelengths, independent of the total number of wavelengths in the network, thus eliminating the need for wide-range converters. We investigate both single-stage and multi-stage interconnects. For the single-stage design, we present a full-connectivity interconnect with a smaller number of switching elements compared to most existing designs. For multi-stage interconnects, we consider 3-stage designs, and present two design methods and investigate optimal interconnects for each of the two methods. Finally, we present a cost model to analyze the hardware complexity of the different designs. Cost analysis shows that, the proposed designs can achieve a significant cost saving compared to most designs. In particular, under various conditions, the proposed designs can achieve up to 40 % reduction in cost compared to best known 3-stage designs.

In this paper, we address the problem of designing wavelength division multiplexing (WDM) optical interconnects with reduced hardware complexity. We propose a new WDM optical interconnect design that reduces both the number of space switches and the cost of wavelength conversion. Wavelength conversion in the proposed design occurs between two pre-defined wavelengths, eliminating the need for expensive wide-range wavelength converters used in most existing designs. In addition, the proposed design follows the recursive structure of the Benes network, and hence, scalability occurs in an orderly fashion. A systematic method for developing interconnects with arbitrary number of wavelengths and fibers is given, and the main properties of the new design are analyzed and compared with existing designs. We show that, the new design requires the minimum number of switching stages and space switches compared to any existing WDM Benes interconnect. Moreover, our design has minimum wavelength conversion cost compared to most existing designs.

The design of a survivable network with path-protection involves the provisioning of a primary and a backup path for every connection request. To optimize bandwidth usage under path-based protection, backup paths are allowed to share bandwidth under single failure model. However, path-based protection does not guarantee fast recovery as switches along a shared backup path may need to be reconfigured according to the particular primary path that needs to be recovered. Pre-cross-connected trail (PXT) addresses this problem by ensuring that backup paths are pre-connected. In practice, different requests may have different tolerance for recovery time. However, PXT does not consider differentiated tolerance and thus may block connections that may tolerate longer recovery times. In this paper, we address the problem of provisioning WDM networks with differentiated quality of protection under the path-based protection scheme. We formulate the problem of path protection with Differentiated Quality-of-Protection (DQoP) under single failure model, and develop an on-line algorithm that relaxes the PXT scheme by enabling the provisioning of requests under two classes of protection services. We consider both node failures as well as link failures. Extensive simulation results on several network topologies and under different traffic models confirm a reduction of up to 13% in blocking probability and up to 4% in bandwidth usage compared to the conventional PXT scheme.

In this paper, we present three switch architectures for WDM (Wavelength Division Multiplexing) Benes network that are based on wavelength exchange optical crossbar (WOC). A WOC is capable of performing a single-step space-switching wavelength-conversion between two wavelengths. A WOC can be implemented by the simultaneous power exchange between two optical signals. Unlike existing designs, the proposed architectures do not require separate stages of wavelength converters. This leads to a switch design that has a smaller total number of components as well as a smaller number of components in the signal path. Moreover, wavelength conversion is performed between two predefined and fixed wavelengths. This avoids the need for expensive full-range wavelength converters used in most of the existing designs. Systematic methods to realize switch architectures with an arbitrary number of wavelengths and fibers are given. The three architectures are evaluated and compared to existing architectures on the basis of hardware cost.

In this paper, we propose energy efficient schemes for data dissemination in sensor networks. Our schemes are based on a hierarchical data dissemination model. The hierarchical data dissemination scheme (HDDS) leverages the fact that a nonuniform grid can be constructed to disseminate data based on sink density without any prior information about the position of the sinks. This approach seems to be promising as preliminary experimental results show that an average energy savings of 10-30% can be achieved using our schemes. Even with large number of sources and sinks, the schemes scale well yielding high throughput.. Experimental results show FDDD is suitable for applications which require higher throughput and minimum latency; fully distinct data dissemination for networks with limited energy consumption but can withstand some delay and loss of data, and limited sharing data dissemination is suitable for applications with large number of sources and sinks and average energy consumption and delay.

This paper addresses multicast routing in 40 Gb/s traffic in heterogeneous optical networks. The multicast routing of multi-rate traffic (MRMT) problem is informally defined as the process of finding the best routing which maximizes the total bandwidth utilization in the network, for a given set of sessions, and a given WDM and TDM equipment budget. In our model, a multicast connection is realized by constructing a multicast tree. The whole process is divided into two steps. Numerical results demonstrate our approach utilizes network resources more efficiently, as compared to the approach based on shortest path algorithm.

This research aims at developing a new photonic switch architecture that has several desired features, such as, small size, high scalability, and easy configuration and control. This architecture holds the promise to enabling the next-generation infrastructure for future high-performance computing architectures.

Formal concept analysis (FCA) is a method for deriving conceptual structures out of data that are represented as objects with features. FCA discovers dependencies within the data based on the relation among objects and features. However, not every pair of objects and features defines a concept. Concept approximation is to find the best or closest concept(s) to approximate a pair of objects and features. Concept approximation is significant in that under the circumstances that we can not find a concept, using concept approximation will give the best or most possible solution. In this paper, we evaluate three approaches through experiments in the application of document retrieval. We provide analysis of these approaches and give our concluding remarks.

Optical wireless networks (OWNs) are expected to have a major role in the evolution of broadband wireless networks and the wireless Internet. This is due in large to the high data rates that OWNs can deliver. The deployment of OWNs in these domains necessitates the need for new techniques and approaches that can secure a place for OWNs in the future of wireless communications. The adaptive model of OWNs is considered a major step towards this goal. It has a great impact on the future of OWNs because of the new design concepts it brought to the optical wireless arena. In this paper, we study the multicast process in adaptive OWNs. We prove the NP-hardness of the multicast optimization problem and accordingly propose two optimization heuristics. Simulation results show that networks adapting our multicast heuristics achieve improvements of up to 42% and 62% on average packet delay and overhead-related metrics, respectively, as compared to networks with conventional multicast.

In this paper, we investigate the link flexibility constraints imposed on the deployment of the optical wireless Internet. We formulate the topology control problem under link delay conditions, and accordingly propose a new optimization algorithm for networks with two-transceiver nodes. Simulation results show that networks applying the proposed algorithm achieve a reduction in average packet delay up to 55% over networks with rigid topologies.

The demand for wireless broadband communications has been growing steadily for last several years. The congestion and the limitations on bandwidths of the radio spectrum have inhibited unrestricted growth of radio wireless systems. Wireless optical, however, holds the promise of delivering data rates that can meet the broadband requirements. As a result, wireless optical is believed to be a viable long term option for many applications of wireless communications. Nevertheless, the advantages of optical wireless have not yet been fully exploited. Basic and applied research is needed at the laboratory and commercial levels to bring the performance of real-life wireless optical systems into higher levels. The Gb/s level data rate has been validated in laboratory, however, available indoor systems only realize a data rate of 155Mb/s. Current research in wireless optical concentrates on increasing the communication capacity and improving the performance. In this paper, we survey the wireless optical discipline emphasizing major design, performance, and safety issues. Research directions that have the potential to close the gap between theory and practice, in wireless optical communications, are also presented.

Due to the lack of optical random access memory, optical fiber delay line (FDL) is currently the only way to implement optical buffering. Feed-forward and feedback are two kinds of FDL structures in optical buffering. Both have advantages and disadvantages. In this paper, we propose a more effective hybrid FDL architecture that combines the merits of both schemes. The core of this switch is the arrayed waveguide grating (AWG) and the tunable wavelength converter (TWC). It requires smaller optical device sizes and fewer wavelengths and has less noise than feedback architecture. At the same time, it can facilitate preemptive priority routing which feed-forward architecture cannot support. Our numerical results show that the new switch architecture significantly reduces packet loss probability.

We investigate the problem of wavelength minimization for multicast traffic under multi-drop path model (WMMT-MPM) in all-optical networks. Under a multi-drop path model, multiple paths are employed to establish a multicast session and each path can drop signals at no more than a predefined number of destination nodes. Given a network topology and set multicast sessions, the WMMT-MPM problem is to find a valid routing for each of the multicast session and assign a wavelength to each path in each of the routings, with the objective of minimizing the total number of wavelengths used to establish all the multicast session. To effectively solve the WMMT-MPM problem, we develop two heuristics for routing and wavelength assignment: MFBH-SL and TSH. Through experiments, we show that the TSH outperforms MFBH-SL in more than 80% of instances for real-life and randomly generated networks. Furthermore, the percentage of wavelength saving is at least 18% when session size is /spl les/40% of network nodes.

A pair of vertices of a graph is called a dominating pair if the vertex set of every path between these two vertices is a dominating set of the graph. A graph is a weak dominating pair graph if it has a dominating pair. Further, a graph is called a dominating pair graph if each of its connected induced subgraphs is a weak dominating pair graph. Dominating pair graphs form a class of graphs containing interval, permutation, cocomparability, and asteroidal triple-free graphs. Our purpose is to study the structural properties of dominating pair graphs. Our main results are a polar theorem for the dominating pairs in weak dominating pair graphs and an existence theorem for minimum cardinality connected dominating sets that induce a simple path in connected dominating pair graphs of diameter not equal to three. Furthermore, we present a forbidden induced subgraph characterization of chordal dominating pair graphs.

The objectives in this paper are twofold: design an approach for the netlist partitioning problem using the cooperative multilevel search paradigm introduced by Toulouse et al. and study the effectiveness of this paradigm for solving combinatorial optimization problems, in particular, those arising in the very large scale integration (VLSI) computer-aided design (CAD) area. The authors present a cooperative multilevel search algorithm CoMHP and describe a parallel implementation on the SGI O2000 system. Experiments on ISPD98 benchmark suite of circuits show, for four-way and eight-way partitioning, a reduction of 3% to 15% in the size of hyperedge cuts compared to those obtained by hMETIS. Bisections of hypergraphs based on the algorithm also outperform hMETIS, although more modestly. The authors present experimental results to demonstrate that the cooperation scheme plays a key role in the performance of CoMHP. In fact, the improvement in the quality of the solutions produced by CoMHP is to a large extent independent of the partitioners used in the implementation of CoMHP. The experimental results also demonstrate the effectiveness of the cooperative multilevel search paradigm for solving the netlist partitioning problem.

In this paper, we investigate the multicast routing problem in sparse splitting networks (MR-SSN). The MR-SSN problem is to find a route from the source node of a session to all destinations of the session such that the total number of fibers used in establishing the session is minimized while the multicast capable nodes are evenly distributed throughout the network. We present a heuristic based on Tabu search that requires only one transmitter for the source node and one wavelength for a multicast session in this paper. We test our heuristic on a wide range of network topologies and random sessions and conclude that the difference between our solution and ILP optimal solution in terms of the number of fibers used for establishing a multicast session is within 10% nearly all the time and within 5% in about half of the time.

We investigate the allocation of multicast nodes and formalize it as splitter placement in wavelength-routed networks (SP-WRN) problem. The SP-WRN problem entails the placement of multicast nodes so that the overall network blocking probability is minimized. To gain a deeper insight into the computational complexity of the SP-WRN problem, we define a graph-theoretic version of the splitter placement problem (SPG), and show that even SPG is NP-complete. We develop three heuristics for the SP-WRN problem with different degrees of trade-off between computation time an quality of solution. The first heuristic uses CPLEX, the second heuristic is based on a greedy approach, and the third heuristic employs simulated annealing. Numerical examples demonstrate that: (i) no more than 50% of the cross-connects need to be multi-case capable, and (ii) the iterative simulated annealing heuristic provides fast near-optimal solutions.

Discovering association rules from time-series data is an important data mining problem. The number of potential rules grows quickly as the number of items in the antecedent grows. It is therefore difficult for an expert to analyze the rules and identify the useful. An approach for generating representative association rules for transactions that uses only a subset of the set of frequent itemsets called frequent closed itemsets was presented by Saquer and Deogun (2000). We employ formal concept analysis to develop the notion of frequent closed episodes. The concept of representative association rules is formalized in the context of event sequences. Applying constraints to target highly, significant rules further reduces the number of rules. Our approach results in a significant reduction of the number of rules generated, while maintaining the minimum set of relevant association rules and retaining the ability to generate the entire set of association rules with respect to the given constraints. We show how our method can be used to discover associations in a drought risk management decision support system and use multiple climatology datasets related to automated weather stations.

Article Free Access Share on Multilevel cooperative search: application to the circuit/hypergraph partitioning problem Authors: Min Ouyang U. Nebraska-Lincoln Dept CS&E U. Nebraska-Lincoln Dept CS&EView Profile , Michel Toulouse U. Manitabo Dept CS U. Manitabo Dept CSView Profile , Krishnaiyan Thulasiraman U. Oklahoma School of CS U. Oklahoma School of CSView Profile , Fred Glover U. Colorado Graduate School of Business U. Colorado Graduate School of BusinessView Profile , Jitender S. Deogun U. Nebraska-Lincoln Dept CS&E U. Nebraska-Lincoln Dept CS&EView Profile Authors Info & Claims ISPD '00: Proceedings of the 2000 international symposium on Physical designMay 2000 Pages 192–198https://doi.org/10.1145/332357.332399Online:01 May 2000Publication History 6citation255DownloadsMetricsTotal Citations6Total Downloads255Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper introduces the optical quality of service (QoS) optimization model for wavelength-routed networks. In the first part of this study we concentrate on power as the main quantitative measure of optical QoS. A mathematical formulation of the problem is presented and heuristic approaches are proposed.

In this paper, we introduce the power-efficient design space for multicast wavelength-routed networks. The power-efficient design space is based on the impact of power on the overall design of wavelength-routed networks. Two cross-connect architectures on this design concept are investigated. One is an existing architecture called splitter-and-delivery (SaD). The other is a new architecture called multicast-only splitter-and-delivery (MOSaD). The MOSaD architecture uses power splitters for multicast connections only, allowing unicast connections to pass without enduring unnecessary power losses. Our cross-connect design provides a strictly nonblocking service for unicast connections while eliminating unnecessary power loss of the SaD cross-connect. Experimental results demonstrate that the MOSaD architecture provides substantial savings in cost and reduction in signal power loss with minimal effects on the blocking performance of the network.

In this paper, we investigate the problem of routing connections in ail-optical networks while allowing for degradation of routed signals by different optical components. To overcome the complexity of the problem, we divide it into two parts. First, we solve the pure RWA problem using fixed routes for every connection. Second, power assignment is accomplished by either using the smallest-gain first (SGF) heuristic or using a genetic algorithm. Numerical examples on a wide variety of networks show that: (a) the number of connections established without considering the signal attenuation was most of the time greater than that achievable considering attenuation; and (b) the genetic solution quality was much better than that of SGF, especially when the conflict graph of the connections generated by the linear solver is denser.

In this article, we develop and analyze four algorithms for feature selection in the context of rough set methodology. The initial state and the feasibility criterion of all these algorithms are the same. That is, they start with a given feature set and progressively remove features, while controlling the amount of degradation in classification quality. These algorithms, however, differ in the heuristics used for pruning the search space of features. Our experimental results confirm the expected relationship between the time complexity of these algorithms and the classification accuracy of the resulting upper classifiers. Our experiments demonstrate that a θ-reduct of a given feature set can be found efficiently. Although we have adopted upper classifiers in our investigations, the algorithms presented can, however, be used with any method of deriving a classifier, where the quality of classification is a monotonically decreasing function of the size of the feature set. We compare the performance of upper classifiers with those of lower classifiers. We find that upper classifiers perform better than lower classifiers for a duodenal ulcer data set. This should be generally true when there is a small number of elements in the boundary region. An upper classifier has some important features that make it suitable for data mining applications. In particular, we have shown that the upper classifiers can be summarized at a desired level of abstraction by using extended decision tables. We also point out that an upper classifier results in an inconsistent decision algorithm, which can be interpreted deterministically or non-deterministically to obtain a consistent decision algorithm. © 1998 John Wiley & Sons, Inc.

A vertex (edge) coloring $\phi:V\rightarrow \{1,2,\ldots ,t\}$ ($\phi':E\rightarrow \{1,2,\ldots,$ $t\}$) of a graph G=(V,E) is a vertex (edge) t-ranking if, for any two vertices (edges) of the same color, every path between them contains a vertex (edge) of larger color. The {\em vertex ranking number} $\chi_{r}(G)$ ({\em edge ranking number} $\chi_{r}'(G)$) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the {\sc Vertex Ranking} and {\sc Edge Ranking} problems. It is shown that $\chi_{r}(G)$ can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize the graphs where the vertex ranking number $\chi_{r}$ and the chromatic number $\chi$ coincide on all induced subgraphs, show that $\chi_{r}(G)=\chi (G)$ implies $\chi (G)=\omega (G)$ (largest clique size), and give a formula for $\chi_{r}'(K_n)$.

Clustering is used in information retrieval systems to enhance the efficiency and effectiveness of the retrieval process. Clustering is achieved by partitioning the documents in a collection into classes such that documents that are associated with each other are assigned to the same cluster. This association is generally determined by examining the index term representation of documents or by capturing user feedback on queries on the system. In cluster-oriented systems, the retrieval process can be enhanced by employing characterization of clusters. In this paper, we present the techniques to develop clusters and cluster characterizations by employing user viewpoint. The user viewpoint is elicited through a structured interview based on a knowledge acquisition technique, namely personal construct theory. It is demonstrated that the application of personal construct theory results in a cluster representation that can be used during query as well as to assign new documents to the appropriate clusters.

Finding a Hamiltonian cycle in a graph is one of the classical NP-complete problems. Complexity of the Hamiltonian problem in permutation graphs has been a well-known open problem. In this paper the authors settle the complexity of the Hamiltonian problem in the more general class of cocomparability graphs. It is shown that the Hamiltonian cycle existence problem for cocomparability graphs is in P. A polynomial time algorithm for constructing a Hamiltonian path and cycle is also presented. The approach is based on exploiting the relationship between the Hamiltonian problem in a cocomparability graph and the bump number problem in a partial order corresponding to the transitive orientation of its complementary graph.

Article An object-oriented modeling of the history of optimal retrievals Share on Authors: Yong Zhang Center for Advanced Computer Studies, University of Southwestern Louisiana, Lafayette, LA Center for Advanced Computer Studies, University of Southwestern Louisiana, Lafayette, LAView Profile , Vijay V. Raghavan Center for Advanced Computer Studies, University of Southwestern Louisiana, Lafayette, LA Center for Advanced Computer Studies, University of Southwestern Louisiana, Lafayette, LAView Profile , Jitender S. Deogun Department of Computer Science and Engineering, University of Nebraska, Lincoln, NE Department of Computer Science and Engineering, University of Nebraska, Lincoln, NEView Profile Authors Info & Claims SIGIR '91: Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrievalSeptember 1991 Pages 241–250https://doi.org/10.1145/122860.122885Published:01 September 1991 1citation259DownloadsMetricsTotal Citations1Total Downloads259Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper, we present a new heuristic algorithm for the classical single row routing problem. The algorithm is based on a graph theoretic decomposition scheme and uses modified cut-numbers. The algorithm was implemented in C on VAX 8200. The experimental results show that the quality of solutions generated by our algorithm could be up to 36% better as compared to the existing algorithms.

A unified approach is developed for solving the general problem of minimizing the number of via holes in a two-layer very large-scale integration (VLSI) channel and switch-box routing environment with movable terminals. All horizontal segments of the nets are assumed to be in one layer, and the vertical segments in the other layer. Each net can have multiple terminals. Three different models are considered: (i) two-row channel routing, (ii) three-sided switch-box routing, and (iii) four-sided switch-box routing. The concept of a maximum parallel set of edges in a bipartite graph is introduced to solve the minimization problem. This leads to a unified graph-theoretic approach for solving the via minimization problem for all three models considered. The complexity of the proposed algorithm is O(N log N), in all three cases, where N is the number of pairs of terminals to be connected.>

In this paper a new language operator, a generalized morphic replication, is introduced. Let Ω be a finite set of morphisms and reversal morphisms from ∑* into Δ*, and ω be in Ω*. A morphic replicator is defined as follows: for each x in ∑* define ω(x) to be h1(x) … hm(x), where |ω| = m and ω = h1 … hm. A generalized morphic replication extends ω to languages by ω(L) = {ω(x): x is in L} and to sets W of morphic replicators, where W ⊆ Ω*, W(x) = {ω(x): ω is in W} and W(L) = UW(x), where the union is taken over all x in L. It is shown that the class of languages accepted in real time by a non-deterministic reversal-bounded multitape Turing machine, the class of NP, and the class of the recursively enumerable sets, are all closed under the generalized morphic replication when the morphisms and the reversal morphisms are, respectively, linear-erasing, polynomial-erasing, and arbitrary.

User-oriented clustering schemes enable the classification of documents based upon the user perception of the similarity between documents, rather than on some similarity function presumed by the designer to represent the user criteria. In this paper, an enhancement of such a clustering scheme is presented. This is accomplished by the formulation of the user-oriented clustering as a function-optimization problem. The problem formulated is termed the Boundary Selection Problem (BSP). Heuristic approaches to solve the BSP are proposed and a preliminary for evaluation of these approaches is provided.

In information retrieval, cluster analysis is an important tool employed to enhance both efficiency and effectiveness of the retrieval process. Most clustering algorithms have difficulty in reflecting the closeness of documents as perceived by the user. A two phase scheme for document clustering, whose results reflect the “conceptual” clusters that are perceived by the user of the retrieval system, is proposed. Since the clusters obtained by this scheme are not characterized in terms of the document representations, a strategy for cluster searching is also developed. Both the proposed document clustering scheme and document searching strategy are experimentally evaluated using a test collection from the SMART system. The preliminary experimental results obtained are very encouraging.

A structured graph is a hierarchy of graphs which provides a representation of a graph at variable detail levels. In this paper we investigate the path problem in a structured graph. The concept of structured graph is defined, and a formal definition of path in such a structure is given. The relationship between structured paths and canonical ones in the graph represented by a structured graph is investigated. Algorithms to construct paths and to compute a structured path from a given canonical one are presented.

This paper studies the problem of storing single-level and multilevel clustered files. Necessary and sufficient conditions for a single-level clustered file to have the consecutive retrieval property (CRP) are developed. A linear time algorithm to test the CRP for a given clustered file and to identify the proper arrangement of objects, if CRP exists, is presented. For the single-level clustered files that do not have CRP, it is shown that the problem of identifying a storage organization with minimum redundancy is NP-complete. Consequently, an efficient heuristic algorithm to generate a good storage organization for such files is developed. Furthermore, it is shown that, for certain types of multilevel clustered files, there exists a storage organization such that the objects in each cluster, for all clusters in each level of the clustering, appear in consecutive locations.

An algorithm for sequencing jobs on a single processor with the objective of minimizing the mean flow time, when the jobs may have unequal ready times, is developed. The procedure involves partitioning the problem into subproblems, and solving the subproblems by applying branch and bound techniques. Experimental evaluation shows that the resulting procedure when the partitioning scheme is applied is more efficient than existing algorithms.

This paper presents a procedure for sequencing a set of jobs on a single processor (machine) with the objective of minimizing the mean flow time, when the jobs may have unequal ready times. The procedure involves implicit enumeration with the branch and bound technique, coupled with some devices to improve the efficiency of the search. The devices include a sufficient optimality condition, a simple but tight lower bound and rules for tree pruning. The approach has potential applications to other sequencing problems.