Most existing person re-identification (ReID) methods focus on improving retrieval accuracy by refining features, which fails to balance accuracy with inference efficiency. We observe that query difficulty varies: global features suffice for simple cases, while fine-grained part features are required for challenging cases, such as occlusion. However, current methods typically use the same feature extraction network for all queries, which may limit accuracy on difficult queries or waste computational resources on easier ones. To address this, we propose a two-stage Coarse-to-Fine Dynamic Retrieval mechanism that adaptively allocates resources based on query difficulty. For "easy" queries, only global features are used in the coarse stage, and inference terminates early. For "hard" queries, part features are extracted in the fine stage for detailed matching. To further reduce computational costs, we introduce Mixture of Experts for part feature extraction, where a router assigns patches to part experts using topology annotations, and only activates body-relevant experts, enabling accurate part identification with significant computation reduction. Extensive experiments demonstrate that our method achieves competitive performance while significantly reducing computational costs compared to state-of-the-art methods.

Multi-modal transportation recommendation plays an important role in navigation applications. It aims to recommend a travel plan with various transport modes, such as bus, metro, taxi, bicycle, and a hybrid. Analysis of real-world large-scale navigation data shows that the correlation between the data can be represented by a graph containing different types of nodes and edges. As an emerging technology, graph neural networks (GNN) have shown powerful capabilities in representing graph data. However, existing solutions based on GNN only consider converting heterogeneous graph data into homogeneous graph data, ignoring the effects of different types of nodes and edges. In addition, those methods usually face the over-smoothing problem, which reduces the accuracy of recommendation. To this end, we propose a multi-modalTransportation recommendation algorithm withHeterogeneous graphAttentionNetworks (THAN) based on carefully constructed heterogeneous graphs. We first design a novel graph embedding method to represent the correlation between the origin and the destination, as well as the correlation between origin-destination (OD) pairs and users. Next, a heterogeneous graph from large-scale data is built to describe the relationship between users, OD pairs, and transport modes. Then, we design a hierarchical attention mechanism with residual blocks to generate node embedding in terms of homogeneity and heterogeneity. Finally, a fusion neural layer is designed to fuse embeddings from different views and predict the proper transport mode for users. Extensive experimental results on a large-scale real-world dataset demonstrate that the performance of THAN outperforms five baselines.

Graph classification has been widely used for knowledge discovery in numerous practical application scenarios, such as social networks and protein-protein interaction networks. Recently, Graph Neural Networks (GNNs), which generalize deep neural networks to graph-structured data, have drawn considerable attention and achieved state-of-the-art performance in graph classification. However, existing GNN models mainly focus on capturing the information of immediate or first-order neighboring nodes within a single layer. The graph substructure and substructure interaction, that play an important role in learning graph representations, are usually overlooked. In this paper, we propose a Substructure Assembling Graph Attention Network (SA-GAT) to extract graph features and improve the performance of graph classification. SA-GAT is able to fully explore higher-order substructure information hidden in graphs by a core module called Substructure Interaction Attention (SIA). Theoretically, we have also proved that SA-GAT satisfies the graph isomorphism theory of graph neural network design, which is that the network should map isomorphic graphs to the same representation and output the same prediction. Extensive experimental results on multiple real-world graph classification datasets demonstrate that the proposed SA-GAT outperforms the state-of-the-art methods including graph kernels and graph neural networks.

The advancement of science and technology provides the possibility of personalized intelligent education. Representation learning of students’ behavior data is challenging because whether time sequences and interactive behaviors or the correlation between knowledge points and students carrying important information. Some researchers propose knowledge tracing to provide ideas for solving this dilemma. However, existing knowledge tracing methods are divided into machine learning and deep learning. Machine learning-based methods require manual feature extraction and a large amount of prior knowledge. Although deep learning-based methods can automatically extract features, most methods either only use the time series information of the data, or use the association between knowledge points. All the methods ignore the association between knowledge points and students. To fill this gap, we propose a Gated Heterogeneous Graph Convolutional Network (GHGCN) model. We utilize the encoder-decoder framework to predict student performance using the representations of nodes, which is learned from heterogeneous convolutional networks and gate recurrent unit. To validate the effectiveness of the proposed GHGCN model, we conduct the experiments on three public datasets: Simulated Data, Assistments 2009, and Assistments 2015. The results indicate that our method can achieve better performance compared with state-of-the-art algorithms.

Somatic variants act as critical players during cancer occurrence and development. Thus, an accurate and robust method to identify them is the foundation of cutting-edge cancer genome research. However, due to low accessibility and high individual-/sample-specificity of the somatic variants in tumor samples, the detection is, to date, still crammed with challenges, particularly when lacking paired normal samples as control. To solve this burning issue, we developed a tumor-only somatic and germline variant identification method (TSomVar) using the random forest algorithm established on sample-specific variant datasets derived from genotype imputation, reads-mapping level annotation and functional annotation. We trained TSomVar by using genomic variant datasets of three major cancer types: colorectal cancer, hepatocellular carcinoma and skin cutaneous melanoma. Compared with existing tumor-only somatic variant identification tools, TSomVar shows excellent performances in somatic variant detection with higher accuracy and better capability of recalling for test datasets from colorectal cancer and skin cutaneous melanoma. In addition, TSomVar is equipped with the competence of accurately identifying germline variants in tumor samples. Taken together, TSomVar will undoubtedly facilitate and revolutionize somatic variant explorations in cancer research.

Urban roads tend to cause traffic congestion for a long time after the occurrence of traffic accidents, which greatly affects daily transportations. Therefore, the prediction of the duration of traffic jams caused by traffic accidents can allocate traffic resources more reasonably and effectively, release induced traffic information, avoid secondary congestion, and quickly handle traffic accidents. It is of great significance to the rapid rescue of traffic accidents and to eliminate traffic safety hazards. In response to this hot issue, many scholars have done a lot of researches through numerous models, such as probability distribution and time series, and artificial neural networks. However, these models usually only consider temporal features or are based on shallow networks. Therefore, this work adopts a hybrid deep spatial-temporal residual neural network HD-SP-ResNet to predict the traffic volume and velocity, as well as the road congestion duration after traffic accident, so as to monitor and dispatch real-time traffic, response to the postaccidental congestion in time, in order to reduce the various losses incurred by congestion and improve people's satisfaction with traffic on the road. To verify the effectiveness of the proposed model, we conduct extensive experiments based on the taxi trajectory data and road accident data in Shanghai. The experiment results show that the proposed model can achieve a relatively accurate prediction on traffic volume and velocity, as well as the post-accidental congestion duration.

Summary Word similarity matchmaking is one of the core research areas of information retrieval. The existing methods based on a synonym dictionary would lead to the problem of semantic gap, which could be caused by the absence of synonyms. To address this problem, we improve semantic similarity retrieval by incorporating word embeddings. Especially, word embeddings are trained by Word2Vec and then use them to depict the semantic similarity between words. Experiments are conducted on two different datasets, ie, one is a public long text dataset (ie, Reuters‐21578), and the other is a short text dataset (ie, 120ask) collected from a healthcare community. The experimental results on the two datasets show that the proposed method further improves the accuracy of the similarity retrieval.

The percentage of individuals frequently using their smartphones in work and life is increasing steadily. The interactions between individuals and their smartphones can produce large amounts of usage data, which contain rich information about smartphone owners usage habits and their daily life. In this paper, a visual analytic tool is proposed to discover and understand individual behavior patterns in smartphone usage data. Four cooperated visualization views and many interactions are provided in this tool to visually explore the temporal features of various interactive events between smartphones and their users, the hierarchical associations among event types, and the detailed distributions of massive event sequences. In the case studies, plenty of interesting patterns are discovered by analyzing the data of two smartphone users with different usage styles.

Abstract The new features of HTML5 greatly increase the convenience for both web developers and users, but they also bring new security threats. Although the web‐security community has started to analyze the security threats brought by HTML5, little has been performed to address the security threats for the client‐side applications. This paper studies security issues of two popular client‐side primitives: WebSocket and Web Storage. The security threats concerned in this paper are private information stealth through WebSocket and cross‐site scripting vulnerabilities caused by lacking of sanitization for WebSocket messages and Web Storage data. We analyze the unsafe data flows of these two HTML5 primitives in detail. Based on that, we present a threat detection tool called TD‐WS, which can automatically detect the privacy leaks and the cross‐site scripting vulnerabilities in WebSocket and Web Storage applications. The results show that TD‐WS effectively detects the security threats of WebSocket and Web Storage applications. Copyright © 2016 John Wiley & Sons, Ltd.

This article presents a Light Intensity--based Positioning System (LIPS) for indoor environments. The system uses off-the-shelf light-emitting diode lamps as signal sources and light sensors as signal receivers. The design is inspired by the observation that a light sensor has deterministic sensitivity to both the distance and incident angle of a light signal, an under-utilized feature of photodiodes now widely found on mobile devices. We develop a stable and accurate light intensity model to capture the phenomenon, based on which a new positioning principle, Multi-Face Light Positioning , is established that uses three collocated sensors to uniquely determine the receiver’s position, assuming merely a single source of light. We have implemented a prototype on both dedicated embedded systems and smartphones. Experimental results show average positioning accuracy within 0.4m across different environments, with high stability against interferences from obstacles, ambient lights, temperature variation, and so on.

Carpooling has long held the promise of reducing gas consumption by decreasing mileage to deliver coriders. Although ad hoc carpools already exist in the real world through private arrangements, little research on the topic has been done. In this article, we present the first systematic work to design, implement, and evaluate a carpool service, called coRide , in a large-scale taxicab network intended to reduce total mileage for less gas consumption. Our coRide system consists of three components, a dispatching cloud server, passenger clients, and an onboard customized device, called TaxiBox . In the coRide design, in response to the delivery requests of passengers, dispatching cloud servers calculate cost-efficient carpool routes for taxicab drivers and thus lower fares for the individual passengers. To improve coRide ’s efficiency in mileage reduction, we formulate an NP-hard route calculation problem under different practical constraints. We then provide (1) an optimal algorithm using Linear Programming, (2) a 2-approximation algorithm with a polynomial complexity, and (3) its corresponding online version with a linear complexity. To encourage coRide ’s adoption, we present a win-win fare model as the incentive mechanism for passengers and drivers to participate. We test the performance of coRide by a comprehensive evaluation with a real-world trial implementation and a data-driven simulation with 14,000 taxi data from the Chinese city Shenzhen. The results show that compared with the ground truth, our service can reduce 33% of total mileage; with our win-win fare model, we can lower passenger fares by 49% and simultaneously increase driver profit by 76%.

Abstract Opportunistic routing (OR) significantly improves transmission reliability and network throughput in wireless mesh networks by utilizing the broadcast nature of the wireless medium. Through the integration of network coding (NC), the complicated coordination to select the best forwarding node (FN) in OR can be bypassed. However, the introduction of NC exacerbates the redundant‐packet‐transmission problem. To mitigate this issue, existing coded OR protocols either adopt the loss‐rate‐based approach, employ orthogonal vectors as coded feedback, or pursue the stream‐based coded OR model. However, these three solutions suffer inaccuracy and obsolescence of the loss‐rate measurement, false‐positive/false‐negative problem, and unavailability of hop‐by‐hop stream‐based OR, respectively. To address the previous problems, we propose a simple but practical coded feedback scheme, cumulative coding coefficient acknowledgement (C3ACK), based on the relevance between forward (coded packets received from upstream nodes) and backward coding traffic (coded packets overheard from downstream nodes), and apply C3ACK to both batch‐based and stream‐based coded OR models in order to prune redundant forward and backward coding traffic. Both testbed evaluation and simulation study show that our code‐pruning schemes can outperform existing approaches in terms of expected throughput and transmission count. Copyright © 2014 John Wiley & Sons, Ltd.

Abstract Because of the broadcast and overhearing capability of wireless networks, network coding can greatly improve throughput in wireless networks. However, our investigation of existing inter‐session network coding protocols found that the short‐term unfairness that existed in 802.11‐based medium access control (MAC) protocols actually decreases the coding opportunity, which in turn compromises the throughput gain of network coding. To alleviate the negative impact of this unfairness, we propose a coding‐aware cross‐layer heuristic approach to optimize the coordination of network coding and MAC layer protocol, named FairCoding, which can significantly increase coding opportunities for inter‐session network coding through a fair short‐term traffic allocation for different coding flows. Experiment evaluation shows that the proposed mechanism can bring more coding opportunities and improve the total throughput of wireless mesh networks by up to 20%, compared with the coding mechanism, without considering the negative impact of the short‐term unfairness. Copyright © 2015 John Wiley & Sons, Ltd.

This paper proposes an efficient opportunistic forwarding algorithm in Delay Tolerant Networks (DTNs) using only local information: inter-meeting times collected locally. It tries to minimize delay with a controlled energy consumption through placing a limitation on the number of total copies per message. The proposed forwarding algorithm makes forwarding decisions based only on local information, which means that no information is needed to be exchanged among the nodes, except for the data to be transferred. The removal of information propagation is particularly important in large-scale DTNs with limited communication opportunities like vehicular communication networks. On the contrary, most existing algorithms either forward messages randomly without facilitating any information, or require the exchange of certain information to make wise forwarding decision. Extensive real trace-driven simulations are conducted, and the proposed algorithm significantly outperforms all of the comvehicular communication networks. Onpared localized algorithms in every simulation.

Equipped with accelerometers and gyroscopes, modern smartphones provide an appealing approach to infrastructure-free navigation for vehicles in indoor environments (for example parking garages). However, a smartphone-based inertial navigation system (INS) faces two serious problems. First, it is subject to errors that accumulate over time rather quickly, which may grow to a level that renders the navigation meaningless. Second, without human input or external references, the smartphone can hardly infer its initial position/velocity, which is the basis for distance calculation, since all that a smartphone can learn is its acceleration. This raises a practical concern, as users often need to start indoor navigation precisely when they are uncertain of their current whereabouts. In this paper, we present Bumping , a Bump-Aided Inertial Navigation method that significantly alleviates the above two problems. At the core of this method is a Bump Matching algorithm, which exploits the position information of the readily available speed bumps to provide useful references for the INS. The proposed method is easy to implement, requires no infrastructures, and incurs nearly zero extra energy. We conducted real experiments in tree parking garages of different environmental characteristics. The Bumping method produces an average position error of 4-5 m in these scenarios, improving the accuracy by up to 87.1 percent, compared to the basic inertial navigation method.

Carpooling has long held the promise of reducing gas consumption by decreasing mileage to deliver co-riders. Although ad hoc carpools already exist in the real world through private arrangements, little research on the topic has been done. In this paper, we present the first systematic work to design, implement, and evaluate a carpool service, called coRide, in a large-scale taxicab network intended to reduce total mileage for less gas consumption. Our coRide system consists of three components, a dispatching cloud server, passenger clients, and an onboard customized device, called TaxiBox. In the coRide design, in response to the delivery requests of passengers, dispatching cloud servers calculate cost-efficient carpool routes for taxicab drivers and thus lower fares for the individual passengers.

Many WLAN-based indoor localization techniques estimate a target's location by comparing received signal strength indicator (RSSI) with stored fingerprints. However, the collection of fingerprints is notoriously tedious and time-consuming. It is challenging to reduce the fingerprint collection and recover absent data without introducing errors. In this article, a new approach based on compressive sensing is presented for recovering absent fingerprints. The hidden structure and redundancy characteristics of fingerprints are revealed in the Merging Matrix. The spatial and temporal relativity of fingerprints leads the rank of the Merging Matrix to be small. But the multipath effect in indoor environments conceals the nature of the matrix. The algorithm Sparsity Rank Singular Value Decomposition (SRSVD) can clear away the interference. Experiment results show that using 10% of the data can recover all of the fingerprint information with error rate less than 16%. The localization accuracy with the recovered fingerprints is similar to the one with the original complete fingerprints.

The Internet has become a platform for delivering and consuming content. Additionally, mobile devices consume a significant chunk of content, which poses a unique challenge for provisioning efficient content delivery and is not addressed in contemporary infrastructures. In this paper, we present a naming system that provides Internet-scale content distribution service with a particular emphasis on content delivery across mobile devices. The basis of the system is a highly flexible and expressive content naming scheme. It is flexible in expressing diverse application requirements. To achieve fast name resolution, we design a two-level indexing network using Distributed Hash Table (DHT). This architecture is open and scalable. It utilizes a key-value storage system built on DHT. Our content delivery protocol relies on content routers to balance the load of delivering content and to throttle denial-of-service attacks. The feasibility of the system is analyzed based on a realistic modeling of the Internet. Simulation studies are performed to verify its usefulness and performance.

Abstract Efficient network management can improve the network performance and reduce the cost of system maintenance and administration. One of the important duties assigned to the network management system in a infrastructure wireless LAN (or simply wireless LAN) is to assign users to appropriate accessible access points (APs). The current AP selection schemes in wireless LANs cause an unbalanced load, which in turn reduces the performance of individual users. This has motivated intensive studies attempting to determine efficient methods to balance loads among different APs. Existing works either provide heuristic solutions without performance guarantees or provide centralized solutions which are not desirable for the AP selection problem. In this paper, we study the localized solutions that can provide performance guarantees. We model the AP selection problem as a matching problem in bipartite graph. Our objective is to maximize total load among all APs. We propose a class of localized heuristics based on different user knowledge models. For some of these localized heuristics, we prove that there exists a constant approximation ratio in terms of expected total load through mathematical analysis. Simulations are conducted to verify our results. Copyright © 2009 John Wiley & Sons, Ltd.

Data gathering is a broad research area in wireless sensor networks. The basic operation in sensor networks is the systematic gathering and transmission of sensed data to a sink for further processing. The lifetime of the network is defined as the time until the first node depletes its energy. A key challenge in data gathering without aggregation is to conserve the energy consumption among nodes so as to maximize the network lifetime. We formalize the problem of tackling the challenge as to construct a min-max-weight spanning tree, in which the bottleneck nodes have the least number of descendants according to their energy. However, the problem is NP-complete. A ¿(log n/log/log n)-approximation algorithm MITT is proposed to solve the problem without location information. Simulation results show that MITT can achieve longer network lifetime than existing algorithms.

This paper describes an effective framework to perform image segmentation and find regions of interest (ROI) in a user input object in an interactive way. Similar image objects are then retrieved from a repository. The repository stores off-line trained feature data of image objects, which was obtained by applying feature extraction and dimension reduction analysis to the ROI. The advantage of our framework is that the task is divided into two independent modules that can be implemented individually. Objects are processed in the image domain and the feature domain respectively. The framework has been successfully applied to image databases and can be easily modified to accommodate video objects.

Opportunistic routing (OR) has received much attention as a new routing paradigm due to its efficient utilization of broadcasting and spacial diversity of the wireless medium. Although numerous OR algorithms and protocols have been proposed to apply to various environments and integrate with numerous techniques, as far as we know, none of the existing works have used mathematical tools such as routing algebra to analyze the compatibility of routing metrics and routing protocols so as to provide a guideline for routing protocol design. In this paper, we design a new OR algebra based on the routing algebra proposed for inter-domain routing, identify the essential properties of OR in the mathematical language of the OR algebra, and analyze the design space in terms of routing metrics for various routing requirements.

Recently, erasure coding has become widely used to compensate for the low packet delivery ratio of multi-hop wireless networks. Most existing works assume that the number of redundant erasure-coded packets is unlimited for a message. In this paper, we relax this assumption and integrate the packet quantity into a routing problem in order to achieve a good balance between energy cost and reliability (packet delivery ratio). In doing so, we encounter two major challenges in regards to our new routing problem: one is determining the optimal quantity of redundant packets and the other is determining the optimal routing path.We introduce a benefit value to reflect the trade-off between cost and reliability, and design a single metric (expected utility) by integrating benefit value, cost, and reliability. Based on the expected utility metric, we explore the optimality in both path coding and source coding models. In the path coding model, we design an optimal algorithm, and in the source coding model we propose a heuristic solution. Results from extensive simulations on our custom simulator verify our claims.

Due to resource scarcity, a paramount concern in ad hoc networks is utilizing limited resources efficiently. The self-organized nature of ad hoc networks makes the network utility-based approach an efficient way to allocate limited resources. However, the effect of link instability has not yet been adequately addressed in literature. To efficiently address the routing problem in ad hoc networks, we integrate the cost and stability into a network utility metric, and adopt the metric to evaluate the routing optimality in a unified, opportunistic routing model. Based on this model, an efficient algorithm is designed, both centralized and distributed implementations are presented, and extensive simulations on NS-2 are conducted to verify our results.

The current access point (AP) association schemes in wireless LANs, such as IEEE 802.11, cause an unbalanced load which reduces the performance of both the entire network and individual users. Intensive studies were motivated to determine efficient methods of balancing loads among APs. Previous works provided either the heuristics without theoretical analysis on the performance, or algorithms that require a centralized node or the propagation of global information. In this paper, we model the AP association problem as the many-to-one matching problem in the bipartite graph. Our objective is to maximize the total load among all APs. We propose a localized algorithm that provides a bounded approximation ratio in terms of total load and does not require the propagation of local information. We also extend the localized algorithm through iterative executions, and allow for adaptation to various environments. Extensive simulations are conducted to verify our results.

Recently, opportunistic routing (OR) has been widely used to compensate for the low packet delivery ratio of multi-hop wireless networks. Previous works either provide heuristic solutions without optimality analysis, or assume that unlimited retransmission is available for delivering a data packet. In this paper, we apply OR to a utility-based routing where the successful delivery of a data packet generates benefit. The objective is to maximize utility, defined as a function of benefit and cost of transmission. As the link reliability of each relay determines eventual packet delivery and hence utility, OR offers the ability to increase reliability through opportunistic relays. We explore the optimality of utility-based routing through OR without allowing retransmission, and observe that the optimal scheme requires exhaustive searching of all paths from source to destination. We then propose a heuristic solution to select relays and determine priorities among them. Finally, we provide distributed implementations for both schemes. Simulations on NS-2 and our customized simulator are conducted to verify the effectiveness of the heuristic compared with the optimal.

Link and node reliability are important metrics in wireless ad hoc networks. Therefore, evaluating and quantifying reliability has become the cornerstone of research in this field. Many existing wireless ad hoc network routing algorithms assume the availability of precise reliability information. This, however, is an unrealistic assumption given the dynamics of wireless ad hoc networks. Also, due to frequent changes in topology, reliability information is hard to collect, and oftentimes, inaccuracies can creep in. Therefore, a realistic method is needed to evaluate reliability by mitigating uncertainty in the estimation process. In this paper, we propose a novel reliability estimation model, account for uncertainty in the estimation, and design an uncertainty mitigation scheme. We then illustrate the effectiveness of our scheme in estimating reliability under various levels of uncertainty using a utility-oriented routing algorithm as a sample application. An extensive simulation study shows that the mitigation scheme significantly increases path stability and the long-term total benefit of the system.

Traditional Dijkstra and Bellman-Ford routing algorithms can only provide the best route to each destination based on a fixed link cost model. We propose a utility-based routing model that can provide different optimal routes for different routing requirements captured by the benefit value of the successful delivery of a data packet in a network with unstable links. The challenges lie in the identification of the relationship between the benefit values and the optimal routes without exhausting all possible routes. This can be exponential to the number of nodes in the worst case. We analyze the relationship between the benefit values and the optimal routes, and the relationship between different optimal routes. Based on this analysis, we propose an efficient algorithm that can compute all optimal routes by exploiting a unique property of the model. We also implement the algorithm in a distributed and parallel way, and conduct intensive simulations to verify our results.

Due to resource scarcity, a paramount concern in ad hoc networks is to utilize the limited resources efficiently. The self-organized nature of ad hoc networks makes the social welfare based approach an efficient way to allocate the limited resources. However, the effect of instability of wireless links has not been adequately addressed in the literature. To efficiently address the routing problem in ad hoc networks, we introduce a new metric, maximum expected social welfare, and integrate the cost and stability of nodes in a unified model to evaluate the optimality of routes. The expected social welfare is defined in terms of expected benefit (of the routing source) minus the expected costs incurred by forwarding nodes. Based on our new metric, we design an optimal and efficient algorithm, and implement the algorithm in both centralized (optimal) and distributed (near-optimal) manners. We also extend our work to incorporate retransmission and study the effect of local and global retransmission restrictions on the selection of routes

This paper addresses the target coverage problem in wireless sensor networks with adjustable sensing range. Communication and sensing consume energy, therefore efficient power management can extend network lifetime. In this paper, we consider a large number of sensors with adjustable sensing range that are randomly deployed to monitor a number of targets. Since targets are redundantly covered by more sensors, in order to conserve energy resources, sensors can be organized in sets, activated successively. In this paper we address the adjustable range set covers (AR-SC) problem that has as its objective finding a maximum number of set covers and the ranges associated with each sensor, such that each sensor set covers all the targets. A sensor can participate in multiple sensor sets, but sum of the energy spent in each set is constrained by the initial energy resources. In this paper we mathematically model solutions to this problem and design heuristics that efficiently compute the sets. Simulation results are presented to verify our approaches.

Summary form only given. We present a probabilistic parameterized algorithm for the problem of vertex cover with time complexity O(p2/sup k/), where k is a parameter of the given instance, and p is a polynomial function on the input size. Furthermore, we implement this algorithm within sticker model by DNA computing, with space complexity O(2/sup k/) and polynomial time complexity O(n/sup 2/), where n is the number of vertexes.