In this paper, a novel Multimodal Smartphone based IoT framework is proposed that interconnects human user with robotic system in performing SLAM based Human Robot Interactive tasks. Through this system, humans are added in the loop to build and update the SLAM map where they send commands to add and change locations on top of the 2D SLAM map and navigate to locations using the SLAM map when users issue a navigation command. Preliminary experiments conducted in a lab environment showed that the system can build and update SLAM maps, using user voice and text commands. Adding or changing a location in the SLAM map through user speech and text commands took an average time of 9.7 seconds while the robotic system took an average time of 40.96 seconds to complete a navigation task based on user commands using the SLAM map with an average distance error of 10.4 cm.

In this paper, a novel Edge-IoT framework is proposed which interconnects the user's smartphones with the robotic system for human-robot interaction. The user sends speech commands using mobile application which is processed by the framework and sent to the robotic system. The robotic system executes the task and sends a completion message to the user through the framework. Preliminary experiments conducted by sending multiple requests to the framework to perform a robotic task showed that the framework is able to handle multiple requests, send commands to the robotic system to perform the robotic task and send completion messages to the user efficiently.

In recent years, computer and game-based cognitive tests have become popular with the advancement in mobile technology. However, these tests require very little body movements and do not consider the influence that physical motion has on cognitive development. Our work mainly focus on assessing cognition in children through their physical movements. Hence, an assessment test "Ball-Drop-to-the-Beat" that is both physically and cognitively demanding has been used where the child is expected to perform certain actions based on the commands. The task is specifically designed to measure attention, response inhibition, and coordination in children. A dataset has been created with 25 children performing this test. To automate the scoring, a computer vision-based assessment system has been developed. The vision system employs an attention-based fusion mechanism to combine multiple modalities such as optical flow, human poses, and objects in the scene to predict a child's action. The proposed method outperforms other state-of-the-art approaches by achieving an average accuracy of 89.8 percent on predicting the actions and an average accuracy of 88.5 percent on predicting the rhythm on the Ball-Drop-to-the-Beat dataset.

Robots are increasingly present in environments shared with humans. Robots can cooperate with their human teammates to achieve common goals and complete tasks. This paper focuses on developing a real-time framework that assesses the cognitive load of a human while cooperating with a robot to complete a collaborative assembly task. The framework uses multi-modal sensory data from Electrocardiography (ECG) and Electrodermal Activity (EDA) sensors, extracts novel features from the data, and utilizes machine learning methodologies to detect high or low cognitive load. The developed framework was evaluated on a collaborative assembly scenario with a user study. The results show that the framework is able to reliably recognize high cognitive load and it is a first step in enabling robots to understand better about their human teammates.

Fatigue is a pervasive symptom following brain injury or disease. It has been known to impact recovery and hence is an important factor in rehabilitation. Robotic rehabilitation may be one way to reduce fatigue because of the robot's capability to adapt to user's performance. This paper explores an adaptive rehabilitation system to provide personalized upper limb rehabilitation. The system collects EMG data from the major muscles responsible for movement and adapts the forces used for rehabilitation (assistive and resistive) in real time based on muscle fatigue. Experimental results and the user survey outcomes show that the system was able to detect the onset of fatigue within ± 10 seconds error margin. Overall, it was found that the subjects experienced lower fatigue and had a higher probability of compliance and engagement with the proposed robotic rehabilitation system.

Smart wearable devices have lead to an increased need for processing and sharing large streams of physiological data in real-time. Modern Human-Machine Interaction (HMI) systems, especially applications designed for user training and assessment (e.g., educational or smart-rehabilitation systems), should be able to track and monitor those signals and adapt their parameters accordingly in order to optimally facilitate the special needs of each individual. Towards this end, we propose a passive Brain-Computer Interface (BCI), using a wireless non-intrusive EEG sensor under a robot assisted training task designed for cognitive assessment. As part of this ongoing work, we demonstrate our initial results on predicting user's task performance, from the EEG signals, before task completion. Our findings highlight the potentials of our hypotheses as we achieve a maximum accuracy rate equal to 74% when evaluated on 69 real subjects.

This paper proposes a novel system for assessing physical exercises specifically designed for cognitive behavior monitoring. The proposed system provides decision support to experts for helping with early childhood development. Our work is based on the well-established framework of Head-Toes-Knees-Shoulders (HTKS) that is known for its sufficient psychometric properties and its ability to assess cognitive dysfunctions. HTKS serves as a useful measure for behavioral self-regulation. Our system, CogniLearn, automates capturing and motion analysis of users performing the HTKS game and provides detailed evaluations using state-of-the-art computer vision and deep learning based techniques for activity recognition and evaluation. The proposed system is supported by an intuitive and specifically designed user interface that can help human experts to cross-validate and/or refine their diagnosis. To evaluate our system, we created a novel dataset, that we made open to the public to encourage further experimentation. The dataset consists of 15 subjects performing 4 different variations of the HTKS task and contains in total more than 60,000 RGB frames, of which 4,443 are fully annotated.

MDP heuristic based POMDP algorithms have been considered as simple, fast, but imprecise solutions. This paper provides a novel MDP heuristic value iteration algorithm for POMDPs. Besides the help of MDP, our algorithm utilizes a weighted graph model for the belief point approximation and reassignment, to further improve the efficiency and decrease the space complexity. Experimental results indicate our algorithm is fast and has high solution quality for POMDP problems.

Array comparative genomic hybridization (aCGH) is a newly introduced method for the detection of copy number abnormalities associated with human diseases with special focus on cancer. Specific patterns in DNA copy number variations (CNVs) can be associated with certain disease types and can facilitate prognosis and progress monitoring of the disease. Machine learning techniques have been used to model the problem of tissue typing as a classification problem. Feature selection is an important part of the classification process, because many biological features are not related to the diseases and confuse the classification tasks. Multiple feature selection methods have been proposed in the different domains where classification has been applied. In this work, we will present a new feature selection method based on structured sparsity-inducing norms to identify the informative aCGH biomarkers which can help us classify different disease subtypes. To validate the performance of the proposed method, we experimentally compare it with existing feature selection methods on four publicly available aCGH data sets. In all empirical results, the proposed sparse learning based feature selection method consistently outperforms other related approaches. More important, we carefully investigate the aCGH biomarkers selected by our method, and the biological evidences in literature strongly support our results.

This paper presents a low-cost, wearable headset for 3D Point of Gaze (PoG) estimation in assistive applications. The device consists of an eye tracking camera and forward facing RGB-D scene camera which, together, provide an estimate of the user gaze vector and its intersection with a 3D point in space. The resulting system is able to compute the 3D PoG in real-time using inexpensive and readily available hardware components.

This paper presents a new, publicly available eye tracking dataset, aimed to be used as a benchmark for Point of Gaze (PoG) detection algorithms. The dataset consists of a set of videos recording the eye motion of human test subjects as they were looking at, or following, a set of predefined points of interest on a computer visual display unit. The eye motion was recorded using a Mobile Eye, head mounted, infrared monocular camera. The ground truth of the point of gaze and head location and direction in the three dimensional space are provided together with the data. The ground truth regarding the point of gaze at is known in advance since the subjects are always looking at predefined targets, whereas, the head position in 3D is captured using a Vicon Motion Tracking System.

Dialogue Systems (DS) have been rapidly evolving during the last few years. In order for them to be able to adapt to their surroundings and to individual users, researchers have focused on adaptation techniques, giving rise to the field of Adaptive Dialogue Systems (ADS). One important sub field of ADS is learning what the system should say or do next. Most of the work done in this direction assumes the system performs simple actions, rather than behaviours described by sub-dialogues, i.e. complex actions. To this end we propose a novel online algorithm that ranks complex actions according to their performance and selects the top-k performing ones. To the best of our knowledge there is currently no work describing methods to learn policies for complex actions in an online fashion. We also propose an online algorithm able to estimate the effects of system actions on the user's state, in order to make more informed decisions about which action to take and guide the learning algorithm towards a desired final user state. Our results show that the proposed complex action learning algorithm outperforms simple Hierarchical Reinforcement Learning algorithms and that we are able to successfully estimate the effect an action will have on the user's state, using emotional states as a case study.

Everyone is familiar with the scenario, people demand or assign tasks to robots, and robots execute the tasks to serve people. We call such a model Serve-on-Demand. With the advancement of pervasive computing, machine learning and artificial intelligence, the robot service of the next generation will inevitably turn to actively and exactly meet people's needs, even without explicit demand. We call it Serve-on-Need. It requires the robots to comprehend the intentions and preferences of people exactly. In this paper, we model the human-computer interaction for Serve-on-Need as a repeated stochastic Bayesian game. We solve the stochastic Bayesian game by an equilibrium analysis and rational learning. We present the service of a coffee robot to illustrate such an approach.

Sensor networks may be used in many monitoring applications where the locations of the monitored objects are quite sensitive and need to be protected. Previous research mainly focuses on protecting source location against mote-class attackers who only have a local view of the network traffic. In this paper, we focus on how to protect the source location against laptop-class attackers who have a global view of the network traffic. This paper proposes four schemes---naive, global, greedy, and probabilistic---to deal with laptop-class attacks. The naive solution uses maintenance messages sent periodically to hide real event reports. The global and greedy solutions improve the naive solution by reducing the latency of event delivery without increasing communication overhead. The probabilistic solution further improves the performance by reducing communication overhead without sacrificing location privacy. Experiments show that the probabilistic solution is practical for providing source location privacy against a laptop-class attacker.

Localization is a fundamental problem in wireless sensor networks. Currently, most localization protocols assume a benign environment. This paper studies how a localization protocol can be affected by attacks, especially those like wormhole attacks that don't need to capture the keys used in the network, and how such an attack can be detected and defended in distributed scheme. By applying several localization algorithms, this paper first shows that wormhole attacks are a serious threat to all these algorithms, based on simulation in NS-2. The paper first evaluates the effects of wormhole attacks on several Range-Free Anchor-Free (RFAF) localization algorithms based on hop-counting and connectivity techniques. Then, the paper presents an RFAF localization algorithm called Wormhole-resilient Geographic Distributed Localization (WGDL), which embeds a wormhole detecting/recovering mechanism: if this mechanism detects wormhole attacks in location computation, then it will restore the localization by freezing the wormhole affected area. Simulations show that the proposed detection method is effective on different network placements, and that the mechanism has both a low False Toleration Rate (FTR) and a low False Detection Rate (FDR) in detecting wormhole attacks.

Sensor networks are used in a variety of applications such as battlefield reconnaissance, environmental monitoring, and traffic monitoring. Security and privacy become important concerns when people are participants in sensor network applications [1]. In this research, we focus on providing a framework in which the privacy of people participating in sensor networks applications is protected.

In this paper, we propose a novel surface matching algorithm for arbitrarily shaped but simply connected 3-D objects. The spherical harmonic (SPHARM) method is used to describe these 3-D objects, and a novel surface registration approach is presented. The proposed technique is applied to various applications of medical image analysis. The results are compared with those using the traditional method, in which the first-order ellipsoid is used for establishing surface correspondence and aligning objects. In these applications, our surface alignment method is demonstrated to be more accurate and flexible than the traditional approach. This is due in large part to the fact that a new surface parameterization is generated by a shortcut that employs a useful rotational property of spherical harmonic basis functions for a fast implementation. In order to achieve a suitable computational speed for practical applications, we propose a fast alignment algorithm that improves computational complexity of the new surface registration method from O(n3) to O(n2).

Localization is a fundamental problem in sensor networks. This paper proposes a new distributed localization algorithm called GDL ("Geographic Distributed Localization") that is based on hop-counting. Although the idea of predicting node position from connectivity information in WSNs is not new, our algorithm improves on other localization algorithms of this type in several key ways. Results from extensive simulation in NS-2 show a significant improvement in the accuracy with which locations can be determined in WSNs with varying density and different number of nodes on irregular placements. In particular, when compared with the MDS-MAP series of algorithms, our algorithm achieves about a 30-40% improvement in accuracy. It also has a lower communication cost (0(n) versus O(nlogn)) than MDS-MAP(P), and has a low constant memory cost per node.

Recent research has identified significant vulnerabilities in recommender systems. Shilling attacks, in which attackers introduce biased ratings in order to influence future recommendations, have been shown to be effective against collaborative filtering algorithms. We postulate that the distribution of item ratings in time can reveal the presence of a wide range of shilling attacks given reasonable assumptions about their duration. To construct a time series of ratings for an item, we use a window size of k to group consecutive ratings for the item into disjoint windows and compute the sample average and sample entropy in each window. We derive a theoretically optimal window size to best detect an attack event if the number of attack profiles is known. For practical applications where this number is unknown, we propose a heuristic algorithm that adaptively changes the window size. Our experimental results demonstrate that monitoring rating distributions in time series is an effective approach for detecting shilling attacks.

Collaborative filtering techniques have become popular in the past several years as an effective way to help people deal with information overload. An important security concern in traditional recommendation systems is that users disclose information that may compromise their individual privacy when providing ratings. Randomized perturbation schemes have been proposed to disguise user ratings while still producing accurate recommendations. However, recent research has suggested that perturbation schemes might not be able to preserve privacy as much as has been believed. We propose two data reconstruction methods that derive original private information from disguised data in existing perturbation collaborative filtering schemes. One method is based on k-means clustering and the other uses singular value decomposition (SVD). We have conducted theoretical and experimental analysis on the difference between original data and reconstructed data. Our experiments show that both methods can derive a considerable amount of original information. This study helps to determine an empirical trade-off between recommendation accuracy and user privacy in perturbation schemes.

We use a low-dimensional linear model to describe the user rating matrix in a recommendation system. A non-negativity constraint is enforced in the linear model to ensure that each user's rating profile can be represented as an additive linear combination of canonical coordinates. In order to learn such a constrained linear model from an incomplete rating matrix, we introduce two variations on Non-negative Matrix Factorization (NMF): one based on the Expectation-Maximization (EM) procedure and the other a Weighted Nonnegative Matrix Factorization (WNMF). Based on our experiments, the EM procedure converges well empirically and is less susceptible to the initial starting conditions than WNMF, but the latter is much more computationally efficient. Taking into account the advantages of both algorithms, a hybrid approach is presented and shown to be effective in real data sets. Overall, the NMF-based algorithms obtain the best prediction performance compared with other popular collaborative filtering algorithms in our experiments; the resulting linear models also contain useful patterns and features corresponding to user communities.

An important security concern with traditional recommendation systems is that users disclose information that may compromise their individual privacy when providing ratings. A randomization approach has been proposed to disguise user ratings while still producing accurate recommendations. However, recent research has suggested that a significant amount of original private information can be derived from perturbed data in a randomization scheme. We suggest that a main limitation of the existing randomization approach is that perturbation is item-invariant--each item has a same perturbation variance. Based on this observation, we introduce a two-way communication privacypreserving scheme in which users perturb their ratings for each item based on the server's guidance instead of using an item-invariant perturbation. Compared to the existing randomization approach, our new scheme can help users disclose much less private information at the same recommendation accuracy level.

Collaborative filtering techniques have become popular in the past decade as an effective way to help people deal with information overload. Recent research has identified significant vulnerabilities in collaborative filtering techniques. Shilling attacks, in which attackers introduce biased ratings to influence recommendation systems, have been shown to be effective against memory-based collaborative filtering algorithms. We examine the effectiveness of two popular shilling attacks (the random attack and the average attack) on a model-based algorithm that uses Singular Value Decomposition (SVD) to learn a low-dimensional linear model. Our results show that the SVD-based algorithm is much more resistant to shilling attacks than memory-based algorithms. Furthermore, we develop an attack detection method directly built on the SVD-based algorithm and show that this method detects random shilling attacks with high detection rates and very low false alarm rates.

Sensor networks are used in a variety of application areas for diverse problems from habitat monitoring to military tracking. Whenever they are used to monitor sensitive objects, the privacy of monitored objects' locations becomes an important concern. When a sensor reports a monitored object by sending a series of messages through the sensor network, the route these messages take in theory creates a trail leading back to their source. By eavesdropping on communications, an attacker may be able to move from node to node to follow this trail. Several approaches aimed at discouraging this kind of eavesdropping have been proposed, including mechanisms for constructing "phantom" routes and approaches that insert fake sources as background noise. A problem with existing approaches is that message latencies become larger and energy costs become higher as a result of introducing protections for the privacy of a source location. This paper proposes a new cyclic entrapment method (CEM) that protects source locations in sensor networks while adding a comparatively low cost in terms of additional message latency and energy.

MOTIVATION: Recent studies have shown that microarray gene expression data are useful for phenotype classification of many diseases. A major problem in this classification is that the number of features (genes) greatly exceeds the number of instances (tissue samples). It has been shown that selecting a small set of informative genes can lead to improved classification accuracy. Many approaches have been proposed for this gene selection problem. Most of the previous gene ranking methods typically select 50-200 top-ranked genes and these genes are often highly correlated. Our goal is to select a small set of non-redundant marker genes that are most relevant for the classification task. RESULTS: To achieve this goal, we developed a novel hybrid approach that combines gene ranking and clustering analysis. In this approach, we first applied feature filtering algorithms to select a set of top-ranked genes, and then applied hierarchical clustering on these genes to generate a dendrogram. Finally, the dendrogram was analyzed by a sweep-line algorithm and marker genes are selected by collapsing dense clusters. Empirical study using three public datasets shows that our approach is capable of selecting relatively few marker genes while offering the same or better leave-one-out cross-validation accuracy compared with approaches that use top-ranked genes directly for classification. AVAILABILITY: The HykGene software is freely available at http://www.cs.dartmouth.edu/~wyh/software.htm CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary material is available from http://www.cs.dartmouth.edu/~wyh/hykgene/supplement/index.htm.

Representation of relative spatial relations between objects is often required in many multimedia database applications because spatial relations between objects in an image convey important information about the image. Quantitative representation of spatial relations taking into account shape, size, orientation and distance is often required. The R-Histogram is such a quantitative representation of spatial relations between two objects. However, this method only considers pixels on the object boundary, assuming that the objects are homeomorphic to a 2-ball. For objects with more complicated topology, we propose in this paper the R*-Histogram, a new extension to the R-Histogram. The R*-Histogram generalizes the R-Histogram by taking into account all the pixels in the objects. We also introduce an efficient O(kN log N) time algorithm to compute the R*-Histogram, which is asymptotically faster than the original O(N2) time algorithm for the R-Histogram even when k=O(n). Here, N=n2 denotes the number of pixels in the processed n x n image and k is the number of different directions considered. The effectiveness of the R*-Histogram is evaluated empirically with a Query By Example (QBE) system on a database of 2000 synthetic images containing objects with complicated shape and topology. Experiments have shown that the similarly search results match human intuition very well.

Peer-to-Peer(P2P) media streaming has emerged as a promising solution to media streaming in large distributed systems such as the Internet. Several P2P media streaming solutions have been proposed by researchers, however they all implicitly assume peers are collaborative, thus they suffer from the selfish peers that are not willing to collaborate. In this paper we introduce an incentive mechanism to urge selfish peers to behave collaboratively. It combines the traditional reputation-based approach and an online streaming behavior monitoring scheme. Our preliminary results show that the overall performance achieved by collaborative peers do not suffer from the existence of non-collaborative peers. The incentive mechanism is orthogonal to the existing media streaming solutions and can be integrated into them.

The increasing popularity of peer-to-peer systems has promoted the development of new techniques to support various kinds of business transactions. However, users are reluctant to conduct high value transactions over P2P systems due to the inherent untrustworthiness of peers. In this paper, we investigate building trust through automated trust negotiation, which is orthogonal to existing reputation-based approaches. Trust negotiation makes it possible to prove a peer satisfies certain trust requirements imposed by the ongoing business. We also introduce locally trusted third parties, which we demonstrate can effectively promote successful trust negotiations in peer-to-peer systems.

This paper describes a hybrid negotiation strategy mechanism using a strategy pool framework that allows negotiation agents more flexibility and robustness in an automated negotiation system. The strategy pool framework supports: a) dynamically assigning an appropriate negotiation strategy to a negotiation agent according to the current negotiation environment and b) creating new negotiation rules by learning from past negotiations. Learning forms we use here for the framework are Feed Forward Back Propagation (FFBP) neural networks and multidimensional inter-transaction association rules mining.

Representation of relative spatial relations between objects is required in many multimedia database applications. Quantitative representation of spatial relations taking into account shape, size, orientation and distance is often required. This cannot be accomplished by assimilating an object to elementary entities such as the centroid or the minimum bounding rectangle. Thus many authors have proposed numerous representations based on the notion of histograms of angles. However, they can only represent directional relations, but not the topological spatial relations inside and overlap. Moreover, distance information is not explicitly taken into account. To address these issues, we propose in this paper a new histogram representation called R-Histogram that extends the histogram of angles by incorporating both angles and labeled distances. Dissimilarity between images is then defined by the distance between corresponding R-Histograms. A prototype Query By Example (QBE) system using the R-Histogram has been implemented. The effectiveness of our algorithm is demonstrated with experiments on two databases of 2000 synthetic images.

We describe the development of a system that automates data collection, metadata extraction and analysis of spatio-temporal multi-modal data, combining data management and data analysis to provide an efficient resource for clinicians. Though the system is extensible to many applications, the current focus is on managing Multiple Sclerosis (MS) lesion data, which are disparate streams of image, numeric, and text data. In order to discover patterns of MS pathology and plan early and effective treatment, multispectral magnetic resonance (MR) image streams collected over time need to be correlated efficiently with each other and with patient performance and clinical data streams.

msmcT Functional hia~etic Resonance tiagery (~~) is a new' medical ima=tig technology pro~ti~mg tictional, as opposed to natomicd, mapptig of the human brain.The promise of this non-invasive technique has opened new' ch~enges for mdtimedia researchers.A the fieId of human functional neurotia=tig e~lodes and the technology of ~W advmces, computational techniques for expertient control, subject stimu~ generation, and joint stimti-activation tiaetig are Iachg.host computational work h= focused on impro~tig the analysis of the brab S=S.Tti paper describes eomputiationa~mechanisms for the dehery md tiactig of multimedia stimti and a correlation framework for stimti and brain responses.NIediaStim, a new integrated data co~ection fraework for stimuIus tracking $hat k currently under development. NlediaSfi etiends the stimti paradi=m to composite multimedia presentations. To stiulate a real-tie sitiation as reafitica~y as possible, it is tiportant to stidy the brainPerrnksion lo ma}:edigi~alor hard copies of fl or part of thk ~!;ork for personal or classroom use k granted ;I:ithout fee pro~,ided ~ha~copies are not made or distributed for profit or commertizl ada~antage, and fiat copies bear this no:i~and ~heftil titation on the firs!page.To copy oihen!.k~lo repub~i~to post on senrers or 10 redistribute 10 lis~, requires prior specific perrnksion anifor a fee.

This paper presents a decomposition of the affine transformation matrix into three matrix operations consisting of only skew and scaling in a single dimension. This decomposition allows the presentation of a new algorithm for separable affine image warping. The algorithm is a three-pass approach incorporating only scaling, translation, and skew in a single dimension in each pass. The three-pass approach prevents the problem of decreased image resolution in intermediate images. The result is an algorithm with improved resulting image quality in conjunction with higher performance.

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming. The best of these algorithms uses a fast matrix multiplication algorithm and takes O(k3.5n3m0.5 log(nDU)) time for the multicommodity flow problem with integer demands and at least O(k2.5n2m0.5 log(nϵ−1DU)) time to find an approximate solution, where k is the number of commodities, n and m denote the number of nodes and edges in the network, D is the largest demand, and U is the largest edge capacity. As a consequence, even multicommodity flow problems with just a few commodities are believed to be much harder than single-commodity maximum-flow or minimum-cost flow problems. In this paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem. The running time of our randomized algorithm is (up to log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation. In fact, we prove that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2n) single-commodity minimum-cost flow problems. Our k-commodity algorithm runs in O (knm log4n) time with high probability. We also describe a deterministic algorithm that uses an O(k)-factor more time. Given any multicommodity flow problem as input, both algorithms are guaranteed to provide a feasible solution to a modified flow problem in which all capacities are increased by a (1 + ϵ)-factor, or to provide a proof that there is no feasible solution to the original problem. We also describe faster approximation algorithms for multicommodity flow problems with a special structure, such as those that arise in "sparsest cut" problems and uniform concurrent flow problems.

We study multipacket routing problems on rings of processors. We prove a new lower bound of 2n/3 routing steps for the case that k, the number of packets per processor, is at most 2. We also give an algorithm that tightens this lower bound. For the case where k > 2, the lower bound is kn/4. The trivial algorithm needs in the worst case k⌊n/2⌋ steps to terminate. An algorithm that completes the routing in kn/4 + 2.5n routing steps is given.

In order for pseudo-exhaustive test pattern generation to be practical (time requirement less than 2/sup /spl omega//, /spl omega//spl les/20), two conditions must be satisfied: 1). The function of every element in the circuit must be controllable from no more than /spl omega/ inputs, and 2). The overall time to exercise all elements in the circuit must not exceed 2/sup /spl omega//. We address both these requirements by inserting a small number of bypass storage cells in the circuit under test and constructing appropriate Linear Feedback Shift Registers (LFSRs) to serve as built-in test pattern generators. Our method is applicable to both the gate-level and the module-level and achieves low hardware overhead by using a new graph model for the representation of the circuit and a metric quantity that couples requirements 1 and 2 above.>

Article VideoScheme: a programmable video editing systems for automation and media recognition Share on Authors: James Matthews View Profile , Peter Gloor View Profile , Fillia Makedon View Profile Authors Info & Claims MULTIMEDIA '93: Proceedings of the first ACM international conference on MultimediaSeptember 1993 Pages 419–426https://doi.org/10.1145/166266.168442Published:01 September 1993 11citation475DownloadsMetricsTotal Citations11Total Downloads475Last 12 Months2Last 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

Even though exact algorithms exist for permutation routine of n/sup 2/ messages on a n*n mesh of processors which require constant size queues, the constants are very large and the algorithms very complicated to implement. A novel, simple heuristic for the above problem is presented. It uses constant and very small size queues (size=2). For all the simulations run on randomly generated data, the number of routing steps that is required by the algorithm is almost equal to the maximum distance a packet has to travel. A pathological case is demonstrated where the routing takes more than the optimal, and it is proved that the upper bound on the number of required steps is O(n/sup 2/). Furthermore, it is shown that the heuristic routes in optimal time inversion, transposition, and rotations, three special routing problems that appear very often in the design of parallel algorithms.>

A self-contained method with very low bypass storage cell (BSC) overhead is presented. The method uses a graph model to represent the circuit under test. This unifying model makes the method applicable to both the gate level and the module level. A non-necessarily-partitioning technique reduces the number of BSCs considerably.>

The authors discuss the development and implementation of an object-oriented experimental environment for global routing heuristics in VLSI layout design. This experimental environment has been implemented in both common lisp (with object-oriented extensions) and Smalltalk, providing a user-friendly graphical interface for problem input, output, interaction and modification of the heuristics. Several heuristics have been implemented, some of which use only local information, while others use global information concerning the instance of the problem. All heuristics seem to have good average case performance, and from the results it is concluded that, also on average, multi-turn routings do not provide a significant improvement over one-turn routings.>

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming.The best of these algorithms [14] uses a fast matrix multiplication algorithm and takes O(k25n2m5 log(nDU))time to find an approximate solution, where k is the number of commodities, n and m denote the number of nodes and edges in the network, D is the largest demand, and U is the largest edge capacity.Substantially more time is needed to find an exact solution.As a consequence, even multicommodit y flow problems with jnst a few commodities are believed to be much harder than single-commodity maximum-flow or minimum-cost flow problems.In thk paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem.The running time of our randomized algorithm is (up to ,log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation.In fact, we prove that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2 n) single-commodity minimum-cost flow problems.Our k-commodity algorithm runs in O(knm log4 n) time with high probability.We also describe a deterministic algorithm that uses an O(k)-factor more time.Given any multicommodit y flow problem as input, both rdgorithms are guaranteed to provide a feasible solution to a modified @ 1991

Even though exact algorithms exist for permutation routing of n/sup 2/ on a n*n mesh of processors which require constant size queues, the constants are very large, and the algorithms very complicated to implement. A novel, simple heuristic is presented for this problem. The main contribution of the parallel algorithm is that it uses constant and very small queues (queue size for exactly two packets is needed). The algorithm has several attractive features: it is very simple and does not require complex operations for the maintenance of the queues. Experimental results on random-generated data show that the number of steps required to complete the routing is almost equal to the maximum distance a packet has to travel.>

Article Free Access Share on A 2n-2 step algorithm for routing in an nxn array with constant size queues Authors: T. Leighton Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile , F. Makedon Department of Computer Science, University of Texas at Dallas, Richardson, TX Department of Computer Science, University of Texas at Dallas, Richardson, TXView Profile , I. G. Tollis Department of Computer Science, University of Texas at Dallas, Richardson, TX Department of Computer Science, University of Texas at Dallas, Richardson, TXView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 328–335https://doi.org/10.1145/72935.72970Published:01 March 1989Publication History 64citation353DownloadsMetricsTotal Citations64Total Downloads353Last 12 Months19Last 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

Polynomial algorithms are described that solve the MIN CUT LINEAR ARRANGEMENT problem on degree restricted trees. For example, the cutwidth or folding number of an arbitrary degree d tree can be found in $O(n(\log n)^{d - 2} )$ steps. This has applications to integrated circuit layout, in particular the layout of Weinberger arrays [41]. This also yields an algorithm for determining the black/white pebble demand of degree three trees. We also show that for degree three trees, cutwidth is identical to search number and give a forbidden subgraph characterization of degree three trees having cutwidth k.

Polynomial algorithms are described that solve the MIN CUT LINEAR ARRANGEMENT problem on degree restricted trees. For example, the cutwidth or folding number of an arbitrary degree d tree can be found in O(n(logn)d-2) steps. This also yields an algorithm for determining the black/white pebble demand of degree three trees. A forbidden subgraph characterization is given for degree three trees having cutwidth k. This yields an interesting corollary: for degree three trees, cutwidth is identical to search number.