Abstract In vehicular edge computing, both edge and cloud can provide computing services (i.e., tasks). The edge can reduce vehicular task delay by processing data nearby, but is resource‐constrained and cannot handle too many tasks simultaneously. The resource‐rich cloud can handle massive tasks, but is far from users and has low quality of service and energy efficiency. Currently, some work has been done on task offloading for edge‐cloud collaboration. However, either the collaboration among multiple devices is not considered and the load is easily imbalanced; or edge‐cloud collaboration is required for offloading decisions with too many parameters, affecting tasks to be processed efficiently. To address these issues, we learn from the swarm intelligence evolution of sparrow foraging, improve a sparrow search algorithm by integrating three strategies of flyer refine producer update, sin/cos perturbation follower update, and adaptive adjustment agitator update, to optimize the vehicular task offloading location for edge‐cloud collaboration. Furthermore, we combine delay relaxation variables and delay‐energy penalty operator to design a lightweight heuristic task offloading algorithm, and greedily compare the task preoffload location sets with different delay constraints based on the improved sparrow search algorithm, to obtain the optimal task offloading with integrated delay and energy. Simulation experiments verify that our approach can improve the algorithm's optimization accuracy, convergence speed, and robustness. Moreover, the average task delay, total task energy consumption, and load balance degree of our approach outperform the five benchmark algorithms, and can comprehensively optimize task delay and energy consumption, and achieve edge devices load balancing.

Accurate detection of gait event intention and sending it to lower limb exoskeleton (LLE) is the key to achieve active rehabilitation. Most existing surface electromyography (sEMG)-based gait event intention detection methods suffer from insufficient generalization and complex detection. In this paper, we propose a novel approach for detecting gait event intention using a single sEMG sensor. The gait event intention is obtained by detecting the peak activity of the rectus femoris during the stance period. First, the root mean square (RMS) features are extracted from the sEMG data of the rectus femoris. Then, the data groups composed of the RMS features are smoothed and all extreme points are calculated. Finally, the midstance (MSt) events are discovered when the latest maximum point satisfies the preset condition. The experimental results of three different gait speeds showed that the proposed approach could adapt to different walking speeds and maintain a high detection accuracy of gait event intention detection. This study provides a convenient and reliable detection approach for gait research of LLE.

Abstract With the popularity and development of sensors‐containing intelligent terminals, mobile crowdsensing system (MCS) based on the Internet of Things (IoT) has become a new paradigm of application. By the MCS, the pervasive smart device users are enabled to collect large‐scale data cost‐effectively, for crowd intelligent extraction and human‐centric service delivery. However, most of the existing MCSs are based on a centralized structure vulnerable to attacks and intrusions. Moreover, the data collected through crowdsensing are diverse and difficult to guarantee user privacy, especially during the payment and data upload stages. In this article, we propose a blockchain‐based privacy‐preserving crowdsensing (BPPC) scheme based on the distributed structure, to protect user privacy. First, we combine the multiblockchain technology and K‐anonymity to construct anonymity groups for the confusion. Second, we present the random algorithm HashProof to select candidates from the anonymity groups to avoid deployment of Trusted Third Party (TTP) or agent server. Ultimately, we design encryption‐based algorithms building trust and authentication mechanisms in the system to guarantee the confidentiality of user data and achieve the accurate distribution of rewards. To verify the effectiveness and efficiency of the BPPC scheme, extensive experiments were conducted.

Abstract The security of most lattice-based cryptography schemes are based on two computational hard problems which are the short integer solution (SIS) and learning with errors (LWE) problems. The computational complexity of SIS and LWE problems are related to approximating shortest vector problem and bounded distance decoding (BDD) problem. Approximating BDD is a special case of approximating closest vector problem (CVP). In this paper, we revisit the study for approximating CVP. We give a proof that approximating the CVP over $\ell _\infty $-norm (CVP$_\infty $) within any constant factor is NP-hard. The result is obtained by the gap-preserving reduction from Min Total Label Cover problem in $\ell _1$-norm to to CVP$_\infty $. This proof is simpler than known proofs [ 10].

As the world is now fighting against rampant virus COVID-19, the development of vaccines on a large scale and making it reach millions of people to be immunised has become quintessential. So far 40.9% of the world got vaccinated. Still, there are more to get vaccinated. Those who got vaccinated have the chance of getting the vaccine certificate as proof to move, work, etc., based on their daily requirements. But others create their own forged vaccine certificate using advanced software and digital tools which will create complex problems where we cannot distinguish between real and fake vaccine certificates. Also, it will create immense pressure on the government and as well as healthcare workers as they have been trying to save people from day 1, but parallelly people who have fake vaccine certificates roam around even if they are COVID/Non-COVID patients. So, to avoid this huge problem, this paper focuses on detecting fake vaccine certificates using a bot powered by Artificial Intelligence and neurologically powered by Deep Learning in which the following are the stages: a) Data Collection, b) Preprocessing to remove noise from the data, and convert to grayscale and normalised, c) Error level analysis, d) Texture-based feature extraction for extracting logo, symbol and for the signature we extract Crest-Trough parameter, and e) Classification using DenseNet201 and thereby giving the results as fake/real certificate. The evaluation of the model is taken over performance measures like accuracy, specificity, sensitivity, detection rate, recall, f1-score, and computation time over state-of-art models such as SVM, RNN, VGG16, Alexnet, and CNN in which the proposed model (D201-LBP) outperforms with an accuracy of 0.94.

A major challenge in electroencephalogram (EEG) signal classification is that the EEG signals recorded from different subjects are drawn from different distributions. When the unlabeled EEG data of the new subject arrive, called target domain, classifying them with a classifier trained on prerecorded EEG data of other subjects, called source domain, will greatly decrease the classification accuracy. Being able to use the classifiers trained on data of source domain to accurately classify the data of target domain could reduce the time of the calibration phase in the actual application of the brain-computer interface. This study considers an offline cross-subject classification scenario. We propose a novel manifold trial selection method, which reduces the distribution distance between the source and target domains by manifold transformation and domain adaptation. The proposed method provides a trial selection strategy to suppress negative transfer by removing some abnormal samples. The proposed method is applied to the motor imagery-based brain–computer interface and compared with several existing algorithms. Experimental results show that the proposed method outperforms the state-of-the-art methods.

We propose a new (theoretical) computational model for the study of massive data processing with limited computational resources. Our model measures the complexity of reading the very large data sets in terms of the data size N and analyzes the computational cost in terms of a parameter k that characterizes the computational power provided by limited local computing resources. We develop new algorithmic techniques that implement algorithms for solving well-known computational problems on the proposed model. In particular, we present an algorithm that finds a k-matching in a general unweighted graph in time O(N + k^{2.5}) and an algorithm that constructs a maximum weighted k-matching in a general weighted graph in time O(N + k^3 log k). Both algorithms have their space complexity bounded by O(k^2).

Mobile crowdsensing system has become a new paradigm application with popularity and development of smart mobile devices. It provides a costless and efficient model to collect sensory data. However, most of mobile crowdsensing systems are based on the centralized structure, which will lead to serious privacy disclosure. In this paper, we combine k-anonymity and blockchain to build a mobile corwdsensing system, in which the users can upload their sensory data and receive corresponding rewards without privacy disclosure concern. With the distributed structure system and encryption algorithm, the system achieves enhanced privacy preservation through breaking the link between data and rewards and their owners.

Recent advances in the computer graphics of woven images in 3-space motivate the development of a model for weavings on arbitrary surfaces of higher genus. Our paradigm differs markedly from what Grünbaum and Shepard have provided for the plane. In particular, we induce our weavings from graph imbeddings on surfaces in 3-space. Additionally, we show that the two most frequently invoked subdivision algorithms in computer graphics, the Catmull--Clark and Doo--Sabin algorithms, correspond nicely to topological surgery operations on the induced weavings. The inherently topological formulation of our model permits a graphic designer to superimpose strand colors and geometric attributes---distances, angles, and curvatures---that conform to manufacturing or artistic criteria.

The sustainable growth of bandwidth has been an inevitable tendency in current Data Center Networks (DCN). However, the dramatic expansion of link capacity offers a remarkable challenge to the transport layer protocols of DCN, i.e., how to converge fast and enable data flow to utilize the high bandwidth effectively. Meanwhile, the new protocol should be compatible to the traditional TCP because the applications with old TCP versions are still widely deployed. Therefore, it is important to achieve a trade-off between the aggressiveness and TCP-friendliness in protocol design. In this article, we first empirically investigate why the existing typical data center TCP variants naturally fail to guarantee both fast convergence and TCP friendliness. Then, we design a new transport protocol for DCN, namely Fast and Friendly Converging (FFC), which makes independent decisions and self-adjustment through retrieving the two-dimensional congestion notification from both RTT and ECN. We further present a mathematic model to analyze its competing behavior and converging process. The results from simulation experiments and real implementation show that FFC can achieve fast convergence, thus benefiting the flow completion time. Moreover, when coexisting with the traditional TCP, FFC also presents a moderate behavior, while introducing trivial deployment overhead only at the end-hosts.

We study the Maximum Satisfiability problem (MaxSAT). Particularly, we derive a branching algorithm of running time O*(1.2989^m) for the MaxSAT problem, where m denotes the number of clauses in the given CNF formula. Our algorithm considerably improves the previous best result O*(1.3248^m) by Chen and Kanj [2004] published 15 years ago. For our purpose, we derive improved branching strategies for variables of degrees 3, 4, and 5. The worst case of our branching algorithm is at variables of degree 4 which occur twice both positively and negatively in the given CNF formula. To serve the branching rules and shrink the size of the CNF formula, we also propose a variety of reduction rules which can be exhaustively applied in polynomial time and, moreover, some of them solve a bottleneck of the previous best algorithm.

The dramatic expansion of link capacity in current data center network causes remarkable challenges to the design of new transport layer protocol, that is, how to converge as fast as possible to help data flow effectively utilize the high bandwidth. Meanwhile, the new protocol should be friendly to the traditional TCP because the non-cooperating applications with old TCP versions are widely existing. Therefore, it is important to achieve a trade-off between the aggressiveness and TCP-friendliness in protocol design. In this paper, we first empirically study why the existing typical data center TCP variants naturally fail to guarantee both fast convergence and TCP friendliness. Then, we design FFC, a transport protocol that makes independent decisions and self-adjustment through retrieving the two-dimensional congestion notification from the RTT and ECN. The results of simulation experiments and real implementations show that the fast convergence of FFC leads to the lower flow completion time compared with DX and DCTCP. Meanwhile, when coexisting with the traditional TCP, FFC also presents a moderate competitiveness, while introducing trivial deployment overhead only at the end hosts.

High-resolution vibration data collection with data quality guaranteeing is important in a class of applications like industrial machine and structural health monitoring. Applying wireless vibration sensor networks (WVSNs) to this class is challenging due to severe resource constraints (e.g., bandwidth and energy). State-of-the-art data reduction approaches (e.g., signal processing, in-network aggregation) suggested to improve these constraints do not satisfy application-specific requirements, e.g., high quality of data (QoD) collection or quality of monitoring (QoM). In this paper, we propose vCollector, a general approach to vibration data collection and monitoring in a resource-constrained WVSN. We enable each sensor to reduce the amount of data (before transmission) in a decentralized manner in two stages: the data acquisition stage and data transmission stage. In the first, we propose a solution to low-complexity signal processing; each sensor analyzes signals using the fast Fourier transform (FFT) under the quadrature amplitude modulation (QAM) and then applies an idea from the Goertzel algorithm (first proposed by Goertzel in 1958) so that the sensor can reduce a significant amount of data without sacrificing the QoD. In the second stage, we propose a decision-making algorithm by which each sensor can make a decision on its acquired data (considered event-sensitive data if it has information about harmful vibrations) so that event-insensitive data communication is reduced. Evaluation results (obtained by simulations using our empirical data traces and by a real system deployment) demonstrate that vCollector significantly reduces energy consumption and guarantees QoM in a WVSN.

Modern data centers host diverse hyper text transfer protocol (HTTP)-based services, which employ persistent transmission control protocol (TCP) connections to send HTTP requests and responses. However, the ON/OFF pattern of HTTP traffic disturbs the increase of TCP congestion window, potentially triggering packet loss at the beginning of ON period. Furthermore, the transmission performance becomes worse due to severe congestion in the concurrent transfer of HTTP response. In this paper, we provide the first extensive study to investigate the root cause of performance degradation of highly concurrent HTTP connections in data center network. We further present the design and implementation of TCP-TRIM, which employs probe packets to smooth the aggressive increase of congestion window in persistent TCP connection and leverages congestion detection and control at end-host to limit the growth of switch queue length under highly concurrent TCP connections. The experimental results of at-scale simulations and real implementations demonstrate that TCP-TRIM reduces the completion time of HTTP response by up to 80%, while introducing little deployment overhead only at the end hosts.

Modern data centers host diverse HTTP-based services, which employ persistent TCP connections to send HTTP requests and responses. However, the ON/OFF pattern of HTTP traffic disturbs the increase of TCP congestion window, potentially triggering packet loss at the beginning of ON period. Furthermore, the transmission performance becomes worse due to severe congestion in the concurrent transfer of HTTP response. In this work, we first reveal that the TCP's aggressive behavior in increasing congestion window causes TCP timeouts and throughput collapse. We further present the design and implementation of TCP-TRIM, which employs probe packets to smooth the aggressive increase of congestion window in persistent TCP connection, and leverages congestion detection and control at end-host to limit the growth of switch queue length under highly concurrent TCP connections. The experimental results of at-scale simulations and real implementations show that TCPTRIM reduces the completion time of HTTP response by up to 80%, while introducing little deployment overhead only at the end hosts.

Network lifetime is a crucial performance metric to evaluate data-gathering wireless sensor networks (WSNs) where battery-powered sensor nodes periodically sense the environment and forward collected samples to a sink node. In this paper, we propose an analytic model to estimate the entire network lifetime from network initialization until it is completely disabled, and determine the boundary of energy hole in a data-gathering WSN. Specifically, we theoretically estimate the traffic load, energy consumption, and lifetime of sensor nodes during the entire network lifetime. Furthermore, we investigate the temporal and spatial evolution of energy hole and apply our analytical results to WSN routing in order to balance the energy consumption and improve the network lifetime. Extensive simulation results are provided to demonstrate the validity of the proposed analytic model in estimating the network lifetime and energy hole evolution process.

Providing deadline-sensitive services is a challenge in data centers. Because of the conservativeness in additive increase congestion avoidance, current transmission control protocols are inefficient in utilizing the super high bandwidth of data centers. This may cause many deadline-sensitive flows to miss their deadlines before achieving their available bandwidths. We propose an Adaptive-Acceleration Data Center TCP, A2DTCP, which takes into account both network congestion and latency requirement of application service. By using congestion avoidance with an adaptive increase rate that varies between additive and multiplicative, A2DTCP accelerates bandwidth detection thus achieving high bandwidth utilization efficiency. At-scale simulations and real testbed implementations show that A2DTCP significantly reduces the missed deadline ratio compared to D2TCP and DCTCP. In addition, A2DTCP can co-exist with conventional TCP as well without requiring more changes in switch hardware than D2TCP and DCTCP.

The (parameterized) Minimum Link-Length Rectilinear Spanning Path problem in the$\mbi d$-dimensional Euclidean space$\mbi {\BBR^d}$($\mbi d$-RSP), for a given set$\mbi S$of$\mbi n$points in$\mbi {\BBR^d}$and a positive integer$\mbi k$, is to find a piecewise-linear path$\mbi P$with at most$\mbi k$line-segments that covers (i.e., contains) all points in$\mbi S$, where all line-segments in$\mbi P$are axis-parallel. We first prove that the problem 2-RSP is NP-complete, improving the previously known result that the problem 10-RSP is NP-complete. We then consider a constrained$\mbi d$-RSP problem in which each line-segment$\mbi s$in the spanning path must cover all the points in the given set$\mbi S$that share the same line with$\mbi s$. We present a new parameterized algorithm with running time$\mbi {{O^{\ast}}((2d)^{k})}$for the constrained$\mbi d$-RSP problem, which significantly improves the previous best result and is the first parameterized algorithm of running time$\mbi {{O^{\ast}}{(2^{O(k)}})}$for the constrained$\mbi d$-RSP problem for a fixed$\mbi d$. We show that these results can be extended to the Minimum Link-Length Rectilinear Traveling Salesman problem.

This Supplement includes a selection of papers presented at the 7th International Symposium on Bioinformatics Research and Application (ISBRA), which was held on May 27-29, 2011 at Central South University in Changsha, China.The technical program of the symposium included 36 extended abstracts presented orally and published in volume 6674 of Springer Verlag's Lecture Notes in Bioinformatics series.Additionally, the program included 38 short abstracts presented either orally or as posters.Authors of both extended and short abstracts presented at the symposium were invited to submit full versions of their work to this Supplement.Following a rigorous review process, 19 of the 40 full papers submitted were selected for publication.Selected papers cover a broad range of bioinformatics topics, ranging from algorithms for structural biology to phylogenetics and biological networks.The first two papers of the Supplement address two important problems in structural biology.Improved methods for predicting protein-protein and protein-DNA binding and identification of binding sites are critical components of rational drug design and functional annotation pipelines.The paper by Guo and Wang proposes an efficient algorithm for finding similar binding sites on the protein surfaces based on sequence alignment, protein surface detection, and 3D structure comparison.Validation experiments show significantly improved average recall and precision values compared with existing approaches.Szabóová et al. propose methods for predicting protein-DNA binding propensity from spatial structure information without the use of evolutionary information.Such methods are particularly useful for optimizing DNA-binding of engineered proteins, for which evolutionary information is not available.Unlike previous approaches that rely on ad-hoc sets of physicochemical

The research in the parameterized 3d-matching problem has yielded a number of new algorithmic techniques and an impressive list of improved algorithms. In this article, a new deterministic algorithm for the problem is developed that integrates and improves a number of known techniques, including greedy localization, dynamic programming, and color coding. The new algorithm, which either constructs a matching of k triples in a given triple set or correctly reports that no such a matching exists, runs in time O * (2.80 3 k ), improving a long list of previous algorithms for the problem.

The articles in this special section include selected papers from the Seventh International Symposium on Bioinformatics Research and Applications.

Various gene-expression signatures for breast cancer are available for prediction of clinical outcome, but due to small overlap between different signatures, it is challenging to integrate existing disjoint signatures to provide a unified insight on the association between gene expression and clinical outcome. In this paper, we proposed a method to identify reliable breast cancer gene signature from a context-constrained protein interaction network(PIN). The context-constrained PIN for breast cancer is built by integrating complete PIN and various gene signatures reported in literature. Then, we used graph centrality to quantify the importance of genes to breast cancer. Finally, we got reliable gene signatures that are consisted by the genes with high graph centrality. The genes which are well- known breast cancer genes, such as TP53 and BRCA1 are ranked extremely high in our results. Compared with previous result by functional enrichment analysis, graph centrality, especially the eigenvector centrality and subgraph centrality based gene signatures are more tightly related to breast cancer. We validated these signatures on genome-wide microarray dataset and found higher relationship between the expression of these signature genes and pathologic parameters. In summary, graph centrality provides a novel way to connect different cancer signatures and to understand the mechanism of relationship between gene expression and clinical outcome of breast cancer. Moreover, this method is applied not only to breast cancer, but also to other gene expression related diseases.

In some harsh environment, wireless sensor networks without the sink are often deployed. In the network, the nodes just have limited energy and are easy to fail. In order to prevent the data loss due to the failure of nodes, each node disseminates its data to be stored at a subset of nodes in the network for preservation. However, each node just knows the information of its neighbors, and just has limited storage space. Therefore, it is a challenge to manage the processes of data dissemination and storage effectively. In this paper, an adaptive probability broadcast-based protocol, named APBDP (Adaptive Probability Broadcast-based Data Preservation), is proposed to tackle the challenge. In APBDP, each node disseminates its data to the network by an adaptive probability broadcast mechanism. The mechanism can not only enable all nodes receive the data packet, but also reduce the redundance of data transmission to conserve the energy of nodes. Moreover, each node stores the data received by using LT (Luby Transform) codes, which are the first rateless erasure codes that are very efficient as the amount of data grows. After above processes are finished, a collector (e.g., a motor vehicle) can recover all data by visiting a small subset of nodes. To the best of our knowledge, APBDP is the first scheme that uses adaptive probability broadcast to achieve the efficient data preservation. Theoretical analyses and simulations show that APBDP can achieve higher performance of data preservation and energy efficiency than existing protocols.

Network flooding is a fundamental communication primitive for Wireless Sensor Networks (WSN). Flooding is used for disseminating code updates and parameter changes, affecting the operation of all nodes in the network. When flooding occurs each node, typically, broadcasts the flooding packet once. The costs for flooding, however, can become significant if neighborhood keys are used for communication (as proposed in recent research on secure localization and key distribution [1]), since, instead of a single broadcast, a node is required to perform several unicast transmissions. In this paper we address the problem of minimizing the number of unicast transmissions required for ensuring 100% network coverage for flooding in WSN secured with neighborhood keys. We show that the problem is NP-hard and propose an approximation algorithm for solving it. Through simulations, we demonstrate that our algorithm ensures 100% network coverage for flooding, while requiring, surprisingly, as low as 0.75 packet transmissions per node.

As advances in the technologies of predicting protein interactions, huge data sets portrayed as networks have been available. Identification of functional modules from such networks is crucial for understanding principles of cellular organization and functions. However, protein interaction data produced by high-throughput experiments are generally associated with high false positives, which makes it difficult to identify functional modules accurately. In this paper, we propose a fast hierarchical clustering algorithm HC-PIN based on the local metric of edge clustering value which can be used both in the unweighted network and in the weighted network. The proposed algorithm HC-PIN is applied to the yeast protein interaction network, and the identified modules are validated by all the three types of Gene Ontology (GO) Terms: Biological Process, Molecular Function, and Cellular Component. The experimental results show that HC-PIN is not only robust to false positives, but also can discover the functional modules with low density. The identified modules are statistically significant in terms of three types of GO annotations. Moreover, HC-PIN can uncover the hierarchical organization of functional modules with the variation of its parameter's value, which is approximatively corresponding to the hierarchical structure of GO annotations. Compared to other previous competing algorithms, our algorithm HC-PIN is faster and more accurate.

In this paper, following our recent developed concept of subnet model in mesh networks, we continue to investigate the characterizations of probabilistic fault tolerance for the mesh networks with faulty node. We consider two fault models: each node has deterministic or stochastic failure probability, then we study the fault tolerance of mesh networks based on our novel technique - subnet model. We derive lower bounds on the connectivity probability for mesh networks. Our study shows that mesh networks of practical size can tolerate a large number of faulty nodes thus are reliable enough for multicomputer systems under deterministic or stochastic node failure probability. Comparing with deterministic node failure probability, stochastic model is close to realistic case.

How to improve the data persistence, i.e., the availability of all source data, is an important issue in wireless sensor networks. The issue requires that each source node can disseminate its data (packet) to a subset of nodes in the network for effective storage. In this paper, a distributed scheme based on LT(Luby Transform)-codes, named LTSIDP, is proposed. LT codes are the first rateless erasure codes that are very efficient as the amount of data grows. In LTSIDP, each node uses overhearing to get information whether a packet has been transmitted by one of its neighbors. When a node needs to transmit a packet, it randomly chooses one of its neighbors that does not transmit the packet as receiver. On the other hand, each node can compute a key parameter of LT codes by using some properties of the packet transmission mechanism, and then store the data accordingly. After the process of storage is finished, a collector (e.g., a motor vehicle) can recover all data by visiting a small subset of nodes. To the best of our knowledge, LTSIDP is the first scheme that uses overhearing to improve the data persistence. Theoretical analyses and simulations show that LTSIDP can achieve higher data persistence and energy efficiency than existing schemes.

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 introduces paper-strip sculptures, a physical mesh data-structure used to represent 2-manifold mesh surfaces for understanding topological and geometrical aspects of shape modeling with visual and tactual examples. With paper strips it is possible to construct simple paper sculptures that can convincingly illustrate a variety of ideas in shape modeling - such as 2-manifold mesh surfaces, discrete Gaussian curvature, and the Gauss-Bonnet theorem - with hands-on experiments. Such sculptures can also represent links, knots and weaving. Paper-strip sculptures are also useful to represent and understand non-orientable surfaces such as the projective plane and the Klein bottle.

It has recently been shown that if we twist an arbitrary subset of edges of a mesh on an orientable surface, the resulting extended graph rotation system (EGRS) can be used to induce a cyclic weaving on the surface. In extended graph rotation systems, an edge is viewed as a paper strip that can be twisted. The sides of the paper strips provide ``two strands'' to construct weaving structures. Either these strands are ``parallel'' to the mesh edge for an ``untwisted edge'', or they both cross over the edge and over each other for a ``twisted edge''. If an arbitrary subset of edges of a mesh on an orientable surface is twisted in the same helical sense, then the EGRS induces a cyclic plain-weaving on the surface, which consists of cycles that cross other cycles (or themselves) by alternatingly going over and under. In this paper, we show that it is always possible to create a single-cycle plain-weaving starting from a mesh on an arbitrary surface, by selecting an appropriate subset of edges to be twisted. We also demonstrate how, starting from a mesh, to construct a large number of single-cycle plain-woven objects. Interestingly, the single-cycle solutions with a minimal number of edge twists correspond to plain-woven objects that are visually similar to Celtic knots. For converting plain-weaving cycles to 3D thread structures, we extend the original projection method, which previously worked only when all mesh edges are twisted. With the extension described here, our projection method can also be used to handle untwisted edges. We have developed a system that converts any manifold mesh into single-cycle plain-woven objects, by interactively controlling the proportion of edges that are twisted. The system also allows us to change the shapes of the threads with a set of parameters, interactively in real-time. We demonstrate here that by using this system, we can create a wide variety of single-cycle plain-woven objects.

Haplotypes are more useful in complex disease gene mapping than single-nucleotide polymorphisms (SNPs). However, haplotypes are difficult to obtain directly using biological experiments, which has prompted research into efficient computational methods for determining haplotypes. The individual haplotyping problem called Minimum Letter Flip (MLF) is a computational problem that, given a set of aligned DNA sequence fragment data of an individual, induces the corresponding haplotypes by flipping minimum SNPs. There has been no practical exact algorithm for solving the problem. Due to technical limits in DNA sequencing experiments, the maximum length of a fragment sequenced directly is about 1kb. In consequence, with a genome-average SNP density of 1.84 SNPs per 1 kb of DNA sequence, the maximum number k1 of SNP sites that a fragment covers is usually small. Moreover, in order to save time and money, the maximum number k2 of fragments that cover an SNP site is usually no more than 19. Building on these fragment data properties, the current paper introduces a new parameterised algorithm with running time O(nk22k2 + mlogm + mk1), where m is the number of fragments and n is the number of SNP sites. In practical biological applications, the algorithm solves the MLF problem efficiently even if m and n are large.

In the anonymous communication mechanisms based on key infrastructure, public key or pre-shared key are widely used to set up relay paths and negotiate shared keys in session. Therefore, these systems always have complicated architecture and high key management cost. However, key infrastructure is hard to deployed in distributed environment. Based on multi-paths network coding, this paper firstly proposes a new information slicing and transmitting method ITNC. Then a novel anonymous communication mechanism AC-ITNC without key infrastructure, which is based on ITNC, is presented. In the new mechanism, the anonymous path setup information is sliced into pieces and each piece is coded by the random coding coefficient. The coding coefficients and coded information pieces are delivered along multiple paths, which makes the anonymous relay paths be set up in the case of non-cryptographic scheme. Theoretical analysis and simulation results show that AC-ITNC can significantly improve the security against conspiracy attack in anonymous communication system without key infrastructure.

A novel congestion control protocol, ARROW-TCP, is proposed to address the issues of stability and convergence in existing transmission control protocols. Theoretical analysis shows that ARROW-TCP is globally stable and achieves exponential convergence to efficiency and fairness in a constant time. Meanwhile, ARROW-TCP obtains ideal performance of zero queuing delay, free packet loss by converging monotonically to the fair allocation and avoiding overshooting link capacity. Moreover, the price mechanism leverages ARROW-TCP into max-min rate allocation in hybrid multi-bottleneck networks. Finally, extensive simulations are conducted to verify our theoretical analysis and the simulation results demonstrate that ARROWTCP outperforms other transmission control protocols in terms of stability, convergence, and packet loss rate.

In recent years, worm signatures suffer from difficulties to detect polymorphic worms because these worms can change their patterns dynamically. In this paper, a class of neighborhood-relation signatures (NRS) are proposed, including 1-NRS, 2-NRS and (1,2)-NRS. NRS can be used for detecting polymorphic worms since these worms often remain the same relationship between bytes in changing their patterns. Two signature generation algorithm based on expectation-maximization (EM) and Gibbs Sampling are designed to generate NRS. We perform extensive experiments to demonstrate the effectiveness of NRS and the correctness of the process of signatures generation. Experiment results show that our approach of defending polymorphic worm based on NRS is more effective than other approach based on existed signatures.

In order to prevent worms from propagating rapidly, it is essential to generate worm signatures quickly and accurately. However, most of recent approaches can not generate accurate signatures for polymorphic worms in environments with noise. In this paper, we present a signature generation algorithm, namely CCSF (color coding signature finding), for polymorphic worms based on color coding. CCSF divides n sequences into m groups and each group contains 20 sequences. Firstly, CCSF generates signatures for each group by adopting color coding and filters them. Then all reserved signatures are clustered to get rid of redundant substrings. In this approach, signature can be generated without any fragment in environments with noise, and it can be used in IDS (intrusion detection system) to detect polymorphic worm. We perform extensive experiments to demonstrate the effectiveness of our approach. Experiment results show distinct advantages in generating accurate signatures over other existed approaches.

In some delay-sensitive and durative surveillance applications, in order to gather data at each round, all nodes in wireless sensor networks are organized as a tree rooted at the sink. The tree should be designed carefully to meet the challenges of constraining the data gathering delay and maximizing the network lifetime. The problem of constructing the tree is NP-complete. Moreover, a contradiction between the two challenges is proved in this paper. A novel delay-constrained and maximum lifetime data gathering Algorithm, named DCML, is proposed to solve this problem. DCML needs not to know the location of nodes, and it can construct an energy-balanced tree with limited height at each round. Theoretical analyses and simulation results show DCML can not only achieve longer network lifetime than some existing algorithms, but also constrain the data gathering delay in the network effectively.

In this paper, we show how to create plain-weaving over an arbitrary surface. To create a plain-weaving on a surface, we need to create cycles that cross other cycles (or themselves) by alternatingly going over and under. We use the fact that it is possible to create such cycles, starting from any given manifold-mesh surface by simply twisting every edge of the manifold mesh. We have developed a new method that converts plain-weaving cycles to 3D thread structures. Using this method, it is possible to cover a surface without large gaps between threads by controlling the sizes of the gaps. We have developed a system that converts any manifold mesh to a plain-woven object, by interactively controlling the shapes of the threads with a set of parameters. We have demonstrated that by using this system, we can create a wide variety of plain-weaving patterns, some of which may not have been seen before.

Wireless sensor networks need very efficient network protocols due to the sensors' limited communication and computation capabilities. Network planarization - finding a planar subgraph of the network that contains all the nodes - has been a very important technique for many network protocols. It first became the foundation of various well known routing protocols, including GPSR, GOAFR and several other protocols. Since then, it has also been used in numerous other applications, including data-centric storage, network localization, topology discovery, etc. However, an important problem remains: network planarization itself is very difficult. So far, efficient planarization algorithms exist only for very restrictive models: the network must be a unit-disk graph, and accurate measurements related to the node locations (e.g., node positions or angles between adjacent links) need to be known. For more practical network models, where the transmission ranges are usually not uniform and sensors cannot obtain their accurate location information via expensive localization devices, no efficient planarization algorithm is available. We present a novel method that robustly planarizes sensor networks of a realistic model: networks with non-uniform transmission ranges and unlocalized sensors (that is, static sensors whose locations are unknown). Our method starts with a simple shortest path between two nodes, and progressively planarizes the whole network. It achieves both efficiency and a good planarization result. We present two planarization algorithms for different settings. Our results not only solve the planarization problem, but also outperform some known results in the graph drawing research field. We demonstrate the practical performance of our method - as well as its application in topology discovery, - through extensive simulations.

MOTIVATION: In genetic studies of complex diseases, haplotypes provide more information than genotypes. However, haplotyping is much more difficult than genotyping using biological techniques. Therefore effective computational techniques have been in demand. The individual haplotyping problem is the computational problem of inducing a pair of haplotypes from an individual's aligned SNP fragments. Based on various optimal criteria and including different extra information, many models for the problem have been proposed. Higher accuracy of the models has been an important issue in the study of haplotype reconstruction. RESULTS: The current article proposes a highly accurate model for the single individual haplotyping problem based on weighted fragments and genotypes with errors. The model is proved to be NP-hard even with gapless fragments. Based on the characteristics of Single Nucleotide Polymorphism (SNP) fragments, a parameterized algorithm of time complexity O(nk(2)2(k(2)) + m log m + mk(1)) is developed, where m is the number of fragments, n is the number of SNP sites, k(1) is the maximum number of SNP sites that a fragment covers (no more than n and usually smaller than 10) and k(2) is the maximum number of the fragments covering a SNP site (usually no more than 19). Extensive experiments show that this model is more accurate in haplotype reconstruction than other models. AVAILABILITY: The program of the parameterized algorithm can be obtained by sending an email to the corresponding author.

Data-centric storage, which supports efficient in-network data query and processing, is an important concept for sensor networks. Previous approaches mostly use hash functions to store data, where data with the same key valueare stored in sensors at or near the same geographic location.We propose a new data-centric storage method based on sorting. Our method is robust for different network models and works for unlocalized homogeneous sensor networks, i.e., it requires no location information. The idea is to sort the data in the network based on their key values, so that queries -- including range queries -- can be easily answered. The sorting method balances the storage load well. We present a sorting algorithm that is both decentralized and efficient.

The (parameterized) feedback vertex set problem on directed graphs, which we refer to as the dfvs problem, is defined as follows: given a directed graph G and a parameter k, either construct a feedback vertex set of at most k vertices in G or report that no such set exists. Whether or not the dfvs problem is fixed-parameter tractable has been a well-known open problem in parameterized computation and complexity, i.e., whether the problem can be solved in time f(k)nO(1) for some function f. In this paper we develop new algorithmic techniques that result in an algorithm with running time 4k k! nO(1) for the dfvs problem, thus showing that this problem is fixed-parameter tractable.

BACKGROUND: Identification of protein complexes is crucial for understanding principles of cellular organization and functions. As the size of protein-protein interaction set increases, a general trend is to represent the interactions as a network and to develop effective algorithms to detect significant complexes in such networks. RESULTS: Based on the study of known complexes in protein networks, this paper proposes a new topological structure for protein complexes, which is a combination of subgraph diameter (or average vertex distance) and subgraph density. Following the approach of that of the previously proposed clustering algorithm DPClus which expands clusters starting from seeded vertices, we present a clustering algorithm IPCA based on the new topological structure for identifying complexes in large protein interaction networks. The algorithm IPCA is applied to the protein interaction network of Sacchromyces cerevisiae and identifies many well known complexes. Experimental results show that the algorithm IPCA recalls more known complexes than previously proposed clustering algorithms, including DPClus, CFinder, LCMA, MCODE, RNSC and STM. CONCLUSION: The proposed algorithm based on the new topological structure makes it possible to identify dense subgraphs in protein interaction networks, many of which correspond to known protein complexes. The algorithm is robust to the known high rate of false positives and false negatives in data from high-throughout interaction techniques. The program is available at http://netlab.csu.edu.cn/bioinformatics/limin/IPCA.

We study the theory and techniques developed in the research of parameterized intractability, emphasizing on parameterized hardness and completeness that imply (stronger) computational lower bounds for natural computational problems. Moreover, the fundamentals of the structural properties in parameterized complexity theory, relationships to classical complexity theory and more recent developments in the area are also introduced.

The (parameterized) FEEDBACK VERTEX SET problem on directed graphs (i.e., the DFVS problem) is defined as follows: given a directed graph G and a parameter k , either construct a feedback vertex set of at most k vertices in G or report that no such a set exists. It has been a well-known open problem in parameterized computation and complexity whether the DFVS problem is fixed-parameter tractable, that is, whether the problem can be solved in time f ( k ) n O (1) for some function f . In this article, we develop new algorithmic techniques that result in an algorithm with running time 4 k k ! n O (1) for the DFVS problem. Therefore, we resolve this open problem.

High-speed networks with large bandwidth-delay product present a unique environment where currently TCP may have a major challenge to its performance (e.g. throughput deterioration). A number of new TCP congestion control algorithms have been suggested to address the problems, but at one time they increase the bandwidth utilization and also bring some other limitations, such as low TCP-friendliness, severe RTT unfairness and high packet drop rate. This paper presents a novel cooperant congestion control protocol (C3P), which uses 1 bit routers' explicit feedback predicted information and round-trip times (RTT) delay signals to adjust the congestion windows appropriately. We evaluate the efficiency, TCP-friendliness and fairness of C3P in high bandwidth-delay product (BDP) networks through NS2 simulations.

A deep understanding of the structural properties of wireless networks is critical for evaluating the performance of network protocols and improving their designs. Many protocols for wireless networks - routing, topology control, information storage/retrieval and numerous other applications - have been based on the idealized unit-disk graph (UDG) network model. The significant deviation of the UDG model from many real wireless networks is substantially limiting the applicability of such protocols. A more general network model, the quasi unit-disk graph (quasi-UDG) model, captures much better the characteristics of wireless networks. However, the understanding of the properties of general quasi-UDGs has been very limited, which is impeding the designs of key network protocols and algorithms. In this paper, we present results on two important properties of quasi-UDGs: separability and the existence of power efficient spanners. Network separability is a fundamental property leading to efficient network algorithms and fast parallel computation. We prove that every quasi-UDG has a corresponding grid graph with small balanced separators that captures its connectivity properties. We also study the problem of constructing an energy-efficient backbone for a quasi-UDG. We present a distributed localized algorithm that, given a quasi-UDG, constructs a nearly planar backbone with a constant stretch factor and a bounded degree. We demonstrate the excellent performance of these auxiliary graphs through simulations and show their applications in efficient routing.

Scalable and efficient routing is a main challenge in the deployment of large ad hoc wireless networks. An essential element of practical routing protocols is their accommodation of realistic network topologies. In this paper, we study geographic routing in general large wireless networks. Geographic routing is a celebrated idea that uses the locations of nodes to effectively support routing. However, to guarantee delivery, recent geographic routing algorithms usually resort to perimeter routing, which requires the removal of communication links to get a planar sub-network on which perimeter routing is performed. Localized network planarization requires the wireless network to be a unit-disk graph (UDG) or its close approximation. For networks that significantly deviate from the UDG model, a common case in practice, substantially more expensive and non-localized network planarization methods have to be used. How to make such methods efficiently adaptable to network dynamics, and how to avoid the removal of an excessive number of links that leads to lowered routing performance, are still open problems. To enable efficient geographic routing in general wireless networks, we present face-tracing based routing, a novel approach that routes the message in the faces of the network that are virtually embedded in a topological surface. Such faces are easily recognizable and constructible, and adaptively capture the important geometric features in wireless networks - in particular, holes, -thus leading to very efficient routing. We show by both analysis and si mulations that the face-tracing based routing is a highly scalable routing protocol that generates short routes, incurs low overhead, adapts quickly to network dynamics, and is very robust to variations in network models.

Determining whether a parameterized problem is kernelizable and has a small kernel size has recently become one of the most interesting topics of research in the area of parameterized complexity and algorithms. Theoretically, it has been proved that a parameterized problem is kernelizable if and only if it is fixed-parameter tractable. Practically, applying a data reduction algorithm to reduce an instance of a parameterized problem to an equivalent smaller instance (i.e., a kernel) has led to very efficient algorithms and now goes hand-in-hand with the design of practical algorithms for solving $\mathcal{NP}$-hard problems. Well-known examples of such parameterized problems include the vertex cover problem, which is kernelizable to a kernel of size bounded by $2k$, and the planar dominating set problem, which is kernelizable to a kernel of size bounded by $335k$. In this paper we develop new techniques to derive upper and lower bounds on the kernel size for certain parameterized problems. In terms of our lower bound results, we show, for example, that unless $\mathcal{P} = \mathcal{NP}$, planar vertex cover does not have a problem kernel of size smaller than $4k/3$, and planar independent set and planar dominating set do not have kernels of size smaller than $2k$. In terms of our upper bound results, we further reduce the upper bound on the kernel size for the planar dominating set problem to $67 k$, improving significantly the $335 k$ previous upper bound given by Alber, Fellows, and Niedermeier [J. ACM, 51 (2004), pp. 363–384]. This latter result is obtained by introducing a new set of reduction and coloring rules, which allows the derivation of nice combinatorial properties in the kernelized graph leading to a tighter bound on the size of the kernel. The paper also shows how this improved upper bound yields a simple and competitive algorithm for the planar dominating set problem.

This paper presents our recent theoretical results on high genus modeling. We introduce a new concept called regular handles. Using regular handles it is possible to increase genus without increasing the number of vertices. Using regular handles a wide variety of mesh structures can be constructed. One of the usages of regular handles is to construct families of regular meshes, which is useful to create a wide variety of high genus mesh structures.

In this paper, we propose a novel active queue management algorithm PFED, which is based on network traffic prediction. The main properties of PFED are: (1) stabilizing queue length at a desirable level with consideration of future traffic, and using a MMSE (minimum mean square error) predictor to predict future network traffic; (2) imposing effective punishment upon misbehaving flow with a full stateless method; (3) maintaining queue arrival rate bounded by queue service rate through more reasonable calculation of packet drop probability. To verify the performance of PFED, PFED is implemented in NS2 and is compared with RED and CHOKe with respect to different performance metrics. Simulation results show that PFED outperforms RED and CHOKe in stabling instantaneous queue length and in fairness. It is also shown that PFED enables the link capacity to be fully utilized by stabilizing the queue length at a desirable level, while not incurring excessive packet loss ratio.

A distributed algorithm called P-REMiT is proposed for building an energy-efficient multicast tree in ad hoc networks. The P-REMiT uses the probability method to balance the total energy consumption (TEC) and system lifetime (SL) of multicast tree. It gets the better performance than S-REMiT on metrics about system life and also obtains the better performance than L-REMiT on metrics about TEC. It improves SL of multicast tree efficiently with little sacrifice on TEC and has good convergence.

This paper presents our preliminary results on regular meshes in which all faces have the same size and all vertices have the same valence. A regular mesh is denoted by (n, m, g) where n is the number of the sides of faces, m is the valence of vertices and g is the genus of the mesh. For g = 0, regular meshes include regular platonic solids, all two sided polygons. For g = 1 regular meshes include regular tilings of infinite plane. Our work shows that there exist infinitely many regular meshes for g > 1. Moreover, we have constructive proofs that describe how to create high genus regular meshes that consist of triangles and quadrilaterals (3, m, g) and (4, m, g).

Based on the framework of parameterized complexity theory, we derive tight lower bounds on the computational complexity for a number of well-known NP-hard problems. We start by proving a general result, namely that the parameterized weighted satisfiability problem on depth-t circuits cannot be solved in time n/sup o(k)/poly(m), where n is the circuit input length, m is the circuit size, and k is the parameter, unless the (t - l)-st level W[t $1] of the W-hierarchy collapses to FPT. By refining this technique, we prove that a group of parameterized NP-hard problems, including weighted SAT, dominating set, hitting set, set cover, and feature set, cannot be solved in time n/sup o(k)/poly(m), where n is the size of the universal set from which the k elements are to be selected and m is the instance size, unless the first level W[l] of the W-hierarchy collapses to FPT. We also prove that another group of parameterized problems which includes weighted q-SAT (for any fixed q /spl ges/ 2), clique, and independent set, cannot be solved in time n/sup o(k)/ unless all search problems in the syntactic class SNP, introduced by Papadimitriou and Yannakakis, are solvable in subexponential time. Note that all these parameterized problems have trivial algorithms of running time either n/sup k/ poly(m) or O(n/sup k/).

We address the inference control problem in data cubes with some data known to users through external knowledge. The goal of inference controls is to prevent exact values of sensitive data from being inferred through answers to online analytical processing (OLAP) queries. We present an information theoretic approach for cardinality-based inference control, which simply counts the number of cells that all queries have covered thus far to determine whether a new query should be answered. Compared to previous approaches in sum-only data cubes, our new approach has a more general framework (applies to MIN, MAX and SUM) and is more effective.

Distributed adaptive routing, which routes through alternative paths in presence of faulty network components, is an important subject in the research of fault tolerant multicomputer systems. In this paper, we study the performance of routing scheme under the model in which each network node has independent failure probability. We concentrate on two different routing scheme on the mesh-connected multicomputer systems. We develop new techniques that enable us to derive formally proven success probability for these routing schemes, and compare and analyze their performance. The formal study shows that distributed adaptive routing schemes have the clear advantage over centralized adaptive routing schemes, not only for the well-known facts that distributed routing schemes require no global knowledge of network faults and computationally more efficient, but also because the distributed routing schemes have higher success probability and are more robust to node failure probability and to network size.

We develop new techniques for deriving very strong computational lower bounds for a class of well-known NP-hard problems, including weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although a trivial enumeration can easily test in time O(nk) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k) no(k) for any function f, even if we restrict the parameter value k to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be Θ(μ(n)) for any reasonable function μ, no algorithm of running time no(k) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds are also derived for other problems in the above class. Our techniques can be extended to derive computational lower bounds on approximation algorithms for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1/ε)no(1/ε) for any function f unless an unlikely collapse occurs in parameterized complexity theory.

Reliability and availability are critical when faults appear in the design of large multicomputer systems. On the other hand, it is very difficult to predict the reliability and availability of multicomputer systems. In this paper, we study the reliability and availability of large multicomputer systems under a more realistic model in which each network node has an independent failure probability. We mainly consider the reliability and availability of large mesh-connected multicomputer systems. The metric is connectivity probability of networks. In a previous work (J. Chen and T. Wang, Proc. 14th Int. Conf. Parallel and Distr. Comp. and Sys., pp. 606-611, 2002), we proved that if the node failure probability is fixed, then the connectivity probability of mesh networks can be arbitrarily small when the network size is sufficiently large. Thus, it is practically important for multicomputer system manufacturers to determine the upper bound for node failure probability, when the probability of network connectivity and the network size are given. We develop another novel technique to formally derive lower bounds on the connectivity probability for mesh networks. Our study shows that mesh networks of practical size can tolerate a large number of faulty nodes and thus are reliable enough for multicomputer systems. For example, we formally prove that as long as the node failure probability is bounded by 0.09% (note that according to current VLSI technology, building network nodes with failure probability under 0.09% is achievable), mesh networks of up to a million nodes remain connected with a probability larger than 99%. The results for mesh network reliability and availability are obtained by formal and thorough mathematical proofs.

The mechanism of forwarding request plays the most important role in crowds anonymous communication protocol. On one hand, it hides the identity of the request initiator against the responder; the participants in protocol, and eavesdroppers. On the other hand, it causes additional latency on communication and payload on participants in the protocol. In this paper, we investigated the influence of the forwarding mechanism with respect to the performance and the security in crowds. Different from the previous approaches, our analysis focuses on the length of forwarding paths, and is independent of the underlying length control strategy. In the study of system performance, we consider the participant payload in crowds and prove that the expected participant payload is equal to the expected length of forwarding paths. Applying this result to the currently used length control strategy in crowds, we derive that the expected participant payload in crowds is 1/(1-f) + 1, where P/sub f/ is the forwarding probability in crowds. This improves Reiter and Rubin's original result and demonstrates that the participant payload in crowds is entirely independent of the size of crowds protocol.

Host-based rerouting mechanism is a routing scheme that stores and forwards data in application layer. With this, users can communicate in a indirect way. Thus, identity information such as IP addresses can be effectively hidden against eavesdropper. In anonymous communication systems, such as mixes, onion routing, and crowds, this mechanism is adopted to provide anonymity. This mechanism, however, can result in extra overhead in performance such as communication delay and participant payload, which may affect the applications of anonymous communication systems. In this paper, we study quantitatively the participant payload induced by host-based rerouting mechanisms. A probability formula for calculating the participant payload is derived, which shows that the number of participants, the number of rerouting paths, and the probability distribution of the length of rerouting paths determine the participant payload. Applying this formula to the practical anonymous communication system, crowds, we get immediately the precise expected participant payload, which significantly improves Reiter and Rubin's original analysis and demonstrates that the participant payload in crowds remains a constant and independent of the variation of the number of participants in crowds. Simulation results are presented to testify our theoretical analysis.

In completeness theories of multiple-valued logic, the characterization of Sheffer functions is an important problem, the solution can be reduced to determining the minimal coverings of precomplete classes. In this paper, some simple separable function sets (m=2) are proved to be the component part of the minimal covering of precomplete classes in P*/sub k/.

In this paper, we describe a technique, with roots in topological graph theory, that we call rind modeling. It provides for the easy creation of surfaces resembling peeled and punctured rinds. We show how the method's two main steps of: 1) creation of a shell or crust like the rind of an orange, and 2) opening holes in the crust by punching or peeling can be encapsulated into a real time semi-automatic interactive algorithm. We include a number of worked examples, some by students in a first modeling course, that demonstrate the ease with which a large variety of intricate rind shapes can be created.

Extensive experience has shown that hypercube networks are highly fault tolerant. What is frustrating is that it seems very difficult to properly formulate and formally prove this important fact, despite extensive research efforts in the past two decades. Most proposed fault tolerance models for hypercube networks are only able to characterize very rare extreme situations thus significantly underestimating the fault tolerance power of hypercube networks, while for more realistic fault tolerance models, the analysis becomes much more complicated. We develop new techniques to analyze a realistic fault tolerance model and derive lower bounds for the probability of hypercube network fault tolerance. Our results are both theoretically significant and practically important. Theoretically, our method offers very general and powerful techniques for formally proving lower bounds on the probability of network connectivity, while practically, our results provide formally proven and precisely given upper bounds on node failure probabilities for manufacturers to achieve a desired probability for network connectivity. Our techniques are also useful for analysis of the performance of routing algorithms.

We present two methods to create realistic Chinese painting. The first method is to create 3D Chinese painting animation using existing software packages. The second method is an expressive paint tool which allows an artist to interactively create 2D Chinese painting.

In this work, we present a method to interactively create multi-segment, curved handles between two star-shaped faces of an orientable 2-manifold mesh or to connect two 2-manifold meshes along such faces. The presented algorithm combines a very simple 2D morphing algorithm with Hermite interpolation to construct the handle. Based on the method, we have developed a user interface tool that allows users to simply and easily create multi-segment curved handles.

We present a prototype system for robust, interactive and user friendly modeling of orientable 2-manifold meshes. To develop the system we introduce new topological entities for effectively manipulating 2-manifold mesh structures. We identify a minimal set of fundamental operators, which is necessary and sufficient for performing all homeomorphic and topological operations on 2-manifold mesh structures. Extremely efficient algorithms are developed for the implementation of these operators. We also developed a set of powerful, user-friendly, and effective operators at the level of user interface. Users of our system can perform a large set of homeomorphic and topological changes with these user interface level operators. Our system is topologically robust in the sense that users will never create invalid 2-manifold mesh structure with these operators. In our system, the homeomorphic and topological surgery operations can be applied alternatively on 2-manifold meshes. With our system, users can blend surfaces, construct crusts and open holes on these crusts. With our system, the shapes that look like solid, non-manifold, or 2-manifold with boundary can be manipulated. The system also provides automatic texture mapping during topology changes.

We study hypercube networks with a very large number of faulty nodes. A simple and natural condition, the local subcube-connectivity, is identified under which hypercube networks with a very large number of faulty nodes still remain connected. The condition of local subcube-connectivity can be detected and maintained in a distributed manner based on localized management. Efficient routing algorithms on locally subcube-connected hypercube networks are developed. Our algorithms are distributed and local-information-based in the sense that each node in the network knows only its neighbors' status and no global information of the network is required by the algorithms. For a locally subcube-connected hypercube network that may contain up to 37.5 percent faulty nodes, our algorithms run in linear time and, for any two given nonfaulty nodes, find a routing path of length bounded by four times the Hamming distance between the two nodes. Theoretical analysis and experimental results are presented which show that, under a variety of probability distributions of node failures, hypercube networks are locally subcube-connected with a very high probability and our routing algorithms run in linear time and construct routing paths of nearly optimal length.

The concept of strong fault-tolerance was introduced to characterize the property of parallel routing. A network G of degree d is said to be strongly fault-tolerant if with at most d-2 faulty nodes, any two nodes u and v in G are connected by min{deg/sub f/(u), deg/sub f/(v)} node-disjoint paths, where deg/sub f/ (u) and deg/sub f/ (v) are the numbers of non-faulty neighbors of the nodes u and v in G, respectively. We show that the hypercube networks are strongly fault-tolerant and develop an algorithm that constructs the maximum number of node-disjoint paths in a hypercube network with faults. Our algorithm is optimal in terms of time and length of node-disjoint paths.

The Doubly Linked Face List (DLFL) structure introduces a powerful modeling paradigm that allows users to alternatively apply topological change operations and subdivision operations on a mesh structure. Moreover the DLFL is topologically robust in the sense that it always guarantees valid 2-manifold surfaces. We further study the relationship between DLFL structure and subdivision algorithms. First, we develop a new corner cutting scheme, which provides a tension parameter to control the shape of the subdivided surface. Second, we develop a careful and efficient algorithm for our corner cutting scheme on the DLFL structure that uses only the basic operations provided by the DLFL structure. This implementation ensures that our new corner cutting scheme preserves topological robustness. The comparative study shows that the corner cutting schemes create better handles and holes than Catmull-Clark (1978) scheme.

Recently, there have been considerable interests in the multiprocessor job scheduling problem, in which a job can be processed in parallel on one of several alternative subsets of processors. In this paper, a polynomial time approximation scheme is presented for the problem in which the number of processors in the system is a fixed constant. This result is the best possible because of the strong NP-hardness of the problem and is a significant improvement over the past results: the best previous result was an approximation algorithm of ratio $7/6 + \epsilon$ for 3-processor systems based on Goemans's algorithm for a restricted version of the problem.

In this paper, we present a methodology to use utilization-based admission control in guaranteed real-time communication in a scalable fashion. We make admission control scalable by using a configuration-time test to determine a safe utilization level of servers. Admission control at run-time then is reduced to simple utilization tests on the servers along the path of the new flow. Furthermore, we discuss how appropriate route selection improve utilization levels, design a safe route selection heuristic algorithm to achieve high utilization of resources, and derive two bounds on the maximum utilization level for given traffic in a network. We compare the results of our route selection heuristics with that of a shortest-path based algorithm, and find that our heuristics can achieve a much higher maximum utilization level than that of the shortest-path based algorithm.

The authors present a paradigm that allows dynamic changing of the topology of 2-manifold polygonal meshes. Our paradigm always guarantees topological consistency of polygonal meshes. Based on our paradigm, by simply adding and deleting edges, handles can be created and deleted, holes can be opened or closed, polygonal meshes can be connected or disconnected. These edge insertion and edge deletion operations are highly consistent with subdivision algorithms. In particular, these operations can be easily included into a subdivision modeling system such that the topological changes and subdivision operations can be performed alternatively during model construction. We demonstrate practical examples of topology changes based on this new paradigm and show that the new paradigm is convenient, effective, efficient, and friendly to subdivision surfaces.

We present an improved algorithm for the Vertex Cover problem on graphs of degree bounded by 3 (3DVC). We show that the 3DVC problem can be solved in time O(1.2192kk), where k is the number of vertices in a minimum vertex cover of the graph. Our algorithm also improves previous algorithms on the Independent Set problem on graphs with degree bounded by 3. © 2000 John Wiley & Sons, Inc.

Meshes are the most commonly used objects in computer graphics. They generalize polyhedra by using non-planar faces. Modeling 2D manifold meshes with a simple user interface is an important problem in computer-aided geometric design. In this paper, we propose a conceptual framework for mesh modeling systems that guarantees topologically correct 2D manifolds. Our solution is based on graph rotation systems developed in topological graph theory. As an internal representation of meshes, we use a doubly-linked face list (DLFL). We have also developed a visual representation of the topology that provides a powerful tool for developing a user interface to manipulate the topology of the mesh.

We obtain a generalized version of the well-known distance function family L/sub p/ norm. We prove that the new functions satisfy distance function properties. By using these functions, convex symmetric shapes can be described as loci, the set of points which are in equal distance from a given point. We also show that these symmetric convex shapes can be easily parameterized. We also show these distance functions satisfy a Lipschitz-type condition. We provide a fast ray marching algorithm for rendering shapes described by these distance functions. These distance functions can be used as building blocks for some implicit modeling tools such as soft objects, constructive soft geometry, function representations (freps) or ray quadrics.

Article A polynomial time approximation scheme for general multiprocessor job scheduling (extended abstract) Share on Authors: Jianer Chen Department of Computer Science, Texas A&M University, College Station, TX Department of Computer Science, Texas A&M University, College Station, TXView Profile , Antonio Miranda Department of Computer Science, Bucknell University, Lewisburg, Pennsylvania Department of Computer Science, Bucknell University, Lewisburg, PennsylvaniaView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 418–427https://doi.org/10.1145/301250.301363Online:01 May 1999Publication History 20citation458DownloadsMetricsTotal Citations20Total Downloads458Last 12 Months5Last 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

Let ${\cal S} = {C 1 , C 2 , . . . , C k }$ be a collection of pairwise disjoint subsets of U = { 1, 2, . . . , n} such that $\bigcup_{i = 1}^k C i = U. A partition matching of $\cal S$ consists of two subsets {a 1 , . . . , a m } and {b 1 , . . ., b m } of U together with a sequence of distinct partitions of $\cal S$: $({\cal A}_1, {\cal B}_1), \ldots, ({\cal A}_m, {\cal B}_m)$ such that a i is contained in a subset in the collection ${\cal A}_i$ and b i is contained in a subset in the collection ${\cal B}_i$ for all i = 1, . . . , m. An efficient algorithm is developed that constructs a maximum partition matching for a given collection $\cal S$. The algorithm can be used to construct optimal parallel routing between two nodes in interconnection networks.

Ear decomposition of a graph has been extensively studied in relation to graph connectivity. In this paper, a connection of ear decomposition to graph embeddings is exhibited. It is shown that constructing a maximum-paired ear decomposition of a graph and constructing a maximum-genus embedding of the graph are polynomial-time equivalent. Applications of this connection are discussed.

We investigate the relationship between circuit bottom fan-in and circuit size when circuit depth is fixed. We show that in order to compute certain functions, a moderate reduction in circuit bottom fan-in will cause significant increase in circuit size. In particular, we prove that there are functions that are computable by circuits of linear size and depth k with bottom fan-in 2 but require exponential size for circuits of depth k with bottom fan-in 1. A general scheme is established to study the trade-off between circuit bottom fan-in and circuit size. Based on this scheme, we are able to prove, for example, that for any integer c, there are functions that are computable by circuits of linear size and depth k with bottom fan-in $O(\log n)$ but that require exponential size for circuits of depth k with bottom fan-in c, and that for any constant $\epsilon> 0$, there are functions that are computable by circuits of linear size and depth k with bottom fan-in $\log n$ but that require superpolynomial size for circuits of depth k with bottom fan-in $O(\log^{1-\epsilon} n)$. A consequence of these results is that the three input read-modes of alternating Turing machines proposed in the literature are all distinct.

We investigate the relationship between circuit bottom fan-in and circuit size when circuit depth is fixed. We show that in order to compute certain functions, a moderate reduction in circuit bottom fan-in will cause significant increase in circuit size. In particular, we prove that there are functions that are computable by circuits of linear size and depth k with bottom fan-in 2 but require exponential size for circuits of depth k with bottom fan-in 1. A general scheme is established to study the trade-off between circuit bottom fan-in and circuit size. Based on this scheme, we are able to prove, for example, that for any integer c, there are functions that are computable by circuits of linear size and depth k with bottom fan-in O(log n) but require exponential size for circuits of depth k with bottom fan-in c, and that for any constant /spl epsiv/>0, there are functions that are computable by circuits of linear size and depth k with bottom fan-in log n but require superpolynomial size for circuits of depth k with bottom fan-in O(log/sup 1-/spl epsiv//n). A consequence of these results is that the three input read-modes of alternating Turing machines proposed in the literature are all distinct.

We present a new technique that gives a more thorough analysis on Johnson's classical algorithm for the maximum satisfiability problem. In contrast to the common belief for two decades that Johnson's algorithm has performance ratio 1/2, we show that the performance ratio is 2/3, and that this bound is tight. Moreover we show that simple generalizations of Johnson's algorithm do not improve the performance ratio bound 2/3.

The relationship between nondeterminism and other computational resources is investigated based on the "guess-then-check" model GC. Systematic techniques are developed to construct natural complete languages for the classes defined by this model. This improves a number of previous results in the study of limited nondeterminism. Connections of the model GC to computational optimization problems are exhibited.

Star networks have recently been proposed as attractive alternatives to the popular hypercube for interconnecting processors on a parallel computer. In this paper, we present an efficient algorithm that constructs an optimal parallel routing in star networks. Our result improves previous results for the problem.

Star networks were proposed recently as an attractive alternative to the well-known hypercube models for interconnection networks. Extensive research has been performed that shows that star networks are as versatile as hypercubes. This paper is an effort in the same direction. Based on the well-known paradigms, we study the one-to-many parallel routing problem on star networks and develop an improved routing algorithm that finds n-1 node-disjoint paths between one node and a set of other n-1 nodes in the n-star network. These parallel paths are proven of minimum length within a small additive constant, and the running time of our algorithm is bounded by O(n/sup 2/). More specifically, given a node s and n-1 other nodes {t/sub 1/, t/sub 2/, ..., t/sub n-1/} in the n-star network, our algorithm constructs n-1 node-disjoint paths P/sub 1/, P/sub 2/, ..., P/sub n-1/, where P/sub i/ is a path from s to t/sub j/ of length at most dist(s, t/sub j/)+6 and dist(s, t/sub j/) is the distance, i.e., the length of a shortest path, from s to t/sub j/, for i=1, 2, ..., n-1.The best bound on the path length by previously known algorithms for the same problem is 5(n-2)/spl ap/10/spl Delta//sub n//3, where /spl Delta//sub n/=max{dist(s, t)} is the diameter of the n-star network.

A structure theorem is proved for the class of graphs of bounded average genus, which leads to a linear-time algorithm for isomorphism of such graphs.

Given a graph G with n vertices and m edges, a k-connectivity query for vertices v' and v" of G asks whether there exist k disjoint paths between v' and v". The authors consider the problem of performing k-connectivity queries for k>

The importance of reversal complexity as a basic computational resource has only been recognized in recent years. It is intimately connected to parallel time complexity and circuit depth. In this paper, some basic techniques necessary for establishing analogues of well-known theorems on space and time complexity are developed. The main results are, for reversal-constructible functions $s(n) \geqq \log n$, \[ \textit{DSPACE} (s(n)) \subseteq \textit{DREVERSAL}(s(n)), \] and a tape reduction theorem. As applications of the tape reduction theorem, a hierarchy theorem is proved and the existence of complete languages for reversal complexity is shown.

Reversal complexity on 1-tape and 2-tape Turing machine models discussed. We show that with respect to reversal complexity there is an intrinsic difference between 1-tape and 2-tape Turing machines. More precisely, we show that in the deterministic case, 2-tape Turing machines can simulate k-tape Turing machines without much increase in reversals while 1-tape Turing machines do not have such a property if P ≠ PSPACE; in the nondeterministic case, reversal complexity is “too” powerful to be a complexity measure on 2-tape Turing machines, but on 1-tape Turing machines it is a reasonable complexity measure which is linearly related to the space complexity.