.tabbox {width:400px; margin-top: 15px;margin-bottom: 5px} .tabmenu {width:400px;height:28px;border-left:1px solid #CCC;border-top:1px solid #ccc;} .tabmenu ul {margin:0;padding:0;list-style-type: none;} .tabmenu li { text-align:center; float:left; display:block; width:99px; overflow:hidden; background-color: #f1f1f1; line-height:27px; border-right:#ccc 1px solid; border-bottom:#ccc 1px solid; display:inline;} .tabmenu .cli {text-align:center;float:left;display:block;width:99px;overflow:hidden;background-color: #fff;line-height:27px;border-right:#ccc 1px solid;border-bottom:#fff 1px solid;display:inline; cursor:pointer; color: #810505; font-weight:bold} #tabcontent {width:399px;background-color:#fff;border-left:#CCC 1px solid;border-right:#CCC 1px solid;border-bottom:#CCC 1px solid; height:60px;} #tabcontent ul {margin:0;padding:5px;list-style-type: none;} #tabcontent .hidden {display:none;} Search Browse by Issue Fig/Tab Adv Search
 HOME ABOUT JCST AUTHORS REVIEWERS PUBLISHED PAPERS FORTHCOMING PAPERS
 Bimonthly    Since 1986 ISSN 1000-9000(Print) /1860-4749(Online) CN 11-2296/TP
Indexed in:
SCIE, Ei, INSPEC, JST, AJ, MR, CA, DBLP, etc.
Publication Details
 Edited by: Editorial Board of Journal Of Computer Science and Technology P.O. Box 2704, Beijing 100190, P.R. China Sponsored by: Institute of Computing Technology, CAS & China Computer Federation Undertaken by: Institute of Computing Technology, CAS Published by: SCIENCE PRESS, BEIJING, CHINA Distributed by: China: All Local Post Offices Other Countries: Springer

 ip访问总数: ip当日访问总数: 当前在线人数:
• Table of Content
 10 September 2008, Volume 23 Issue 5 Previous Issue    Next Issue
Special Section on Algorithms and Complexity
 Select t-Private and t-Secure Auctions Markus Hinkelmann, Andreas Jakoby, and Peer Stechert Journal of Computer Science and Technology, 2008, 23 (5 ): 694-710 .  Abstract   PDF(645KB) ( 1266 )   Chinese Summary In most of the auction systems the values of bids are known to the auctioneer. This allows him to manipulate the outcome of the auction. Hence, one might be interested in hiding these values. Some cryptographically secure protocols for electronic auctions have been presented in the last decade. Our work extends these protocols in several ways. On the basis of garbled circuits, i.e., encrypted circuits, we present protocols for sealed-bid auctions that fulfill the following requirements: 1) protocols are information-theoretically $t$-private for {\em honest but curious parties}; 2) the number of bits that can be learned by {\em malicious adversaries} is bounded by the output length of the auction; 3) the computational requirements for participating parties are very low: only random bit choices and bitwise computation of the {\tt XOR}-function are necessary. Note that one can distinguish between the protocol that generates a garbled circuit for an auction and the protocol to evaluate the auction. In this paper we address both problems. We will present a $t$-private protocol for the construction of a garbled circuit that reaches the lower bound of $2t+1$ parties, and a more randomness efficient protocol for $(t+1)^2$ parties. Finally, we address the problem of bid changes in an auction.
 Select Design and Performance Evaluation of Sequence Partition Algorithms Bing Yang, Jing Chen, En-Yue Lu$^3, and Si-Qing Zheng$^{2,4}$Journal of Computer Science and Technology, 2008, 23 (5 ): 711-718 . Abstract PDF(911KB) ( 1397 ) Chinese Summary Tradeoffs between time complexities and solution optimalities are important when selecting algorithms for an NP-hard problem in different applications. Also, the distinction between theoretical upper bound and actual solution optimality for realistic instances of an NP-hard problem is a factor in selecting algorithms in practice. We consider the problem of partitioning a sequence of$n$distinct numbers into minimum number of monotone (increasing or decreasing) subsequences. This problem is NP-hard and the number of monotone subsequences can reach$\big\lfloor \sqrt{2n+\frac 14}-\frac 12 \big\rfloor$in the worst case. We introduce a new algorithm, the modified version of the Yehuda-Fogel algorithm, that computes a solution of no more than$\big\lfloor \sqrt{2n+\frac 14}-\frac 12 \big\rfloor$monotone subsequences in$O(n^{1.5})$time. Then we perform a comparative experimental study on three algorithms, a known approximation algorithm of approximation ratio 1.71 and time complexity$O(n^3)$, a known greedy algorithm of time complexity$O(n^{1.5}\log n)$, and our new modified Yehuda-Fogel algorithm. Our results show that the solutions computed by the greedy algorithm and the modified Yehuda-Fogel algorithm are close to that computed by the approximation algorithm even though the theoretical worst-case error bounds of these two algorithms are not proved to be within a constant time of the optimal solution. Our study indicates that for practical use the greedy algorithm and the modified Yehuda-Fogel algorithm can be good choices if the running time is a major concern.  Select Some Aspects of Synchronization of DFA Avraham Trahtman Journal of Computer Science and Technology, 2008, 23 (5 ): 719-727 . Abstract PDF(299KB) ( 1450 ) Chinese Summary A word$w$is called synchronizing (recurrent, reset, directable) word of deterministic finite automata (DFA) if$w$brings all states of the automaton to a unique state. According to the famous conjecture of Cerny from 1964, every$n$-state synchronizing automaton possesses a synchronizing word of length at most$(n-1)^2$. The problem is still open. It will be proved that the Cerny conjecture holds good for synchronizing DFA with transition monoid having no involutions and for every$n$-state ($n>2$) synchronizing DFA with transition monoid having only trivial subgroups the minimal length of synchronizing word is not greater than$(n-1)^2/2$. The last important class of DFA involved and studied by Schutzenberger is called {\it aperiodic}; its automata accept precisely star-free languages. Some properties of an arbitrary synchronizing DFA were established. See http://www.cs.biu.ac.il/˜trakht/syn.html.  Select Searching a Polygonal Region by Two Guards Xue-Hou Tan and Bo Jiang Journal of Computer Science and Technology, 2008, 23 (5 ): 728-739 . Abstract PDF(1044KB) ( 1723 ) Chinese Summary We study the problem of searching for a mobile intruder in a polygonal region$P$by two guards. The objective is to decide whether there should exist a {\it search schedule} for the two guards to detect the intruder, no matter how fast the intruder moves, and if so, generate a search schedule. During the search, the two guards are required to walk on the boundary of$P$continuously and be mutually visible all the time. We present a characterization of the class of polygons searchable by two guards in terms of non-redundant components, and thus solve a long-standing open problem in computational geometry. Also, we give an optimal$O(n)$time algorithm to determine the two-guard searchability in a polygon, and an$O(n \log n + m)$time algorithm to generate a search schedule, if it exists, where$n$is the number of vertices of$P$and$m(\le n^{2})$is the number of search instructions reported.  Select On Constrained Facility Location Problems Wei-Lin Li, Peng Zhang, and Da-Ming Zhu Journal of Computer Science and Technology, 2008, 23 (5 ): 740-748 . Abstract PDF(428KB) ( 1974 ) Chinese Summary  Select Approximation Algorithms for 3D Orthogonal Knapsack Florian Diedrich, Rolf Harren, Klaus Jansen, Ralf Thöle, and Henning Thomas Journal of Computer Science and Technology, 2008, 23 (5 ): 749-762 . Abstract PDF(667KB) ( 1373 ) Chinese Summary We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9+ and 8+, as well as an algorithm with approximation ratio 7+ that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z-axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6+ and 5+, respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio$29/4$, improving the previously best known result of$45/4$.  Select Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs Jian-Xin Wang, Xiao-Shuang Xu, and Jian-Er Chen Journal of Computer Science and Technology, 2008, 23 (5 ): 763-768 . Abstract PDF(187KB) ( 1390 ) Chinese Summary The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant > 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size , our algorithm constructs a vertex cover of size , satisfying .  Select Analysis and Implementation of an Open Programmable Router Based on Forwarding and Control Element Separation Wei-Ming Wang, Li-Gang Dong, and Bin Zhuge Journal of Computer Science and Technology, 2008, 23 (5 ): 769-779 . Abstract PDF(962KB) ( 2085 ) Chinese Summary A router architecture based upon ForCES (Forwarding and Control Element Separation), which is being standardized by IETF ForCES working group, gains its competitive advantage over traditional router architectures in flexibility, programmability, and cost-effectiveness. In this paper, design and implementation of a ForCES-based router (ForTER) is illustrated. Firstly, the implementation architecture of ForTER is discussed. Then, a layered software model, which well illustrates ForCES features, is proposed. Based on the model, design and implementation of Control Element (CE) and Forwarding Element (FE) in ForTER are introduced in detail. Moreover, security for ForTER is considered and an algorithm to prevent DoS attacks is presented. Lastly, experiments of ForTER are illustrated for routing and running routing protocols, network management, DoS attack prevention, etc. The experimental results show the feasibility of the ForTER design. Consequently, the ForTER implementation basically testifies the feasibility of ForCES architecture and some IETF ForCES specifications.  Select Scalable Base-Station Model-Based Multicast in Wireless Sensor Networks Shao-Liang Peng, Shan-Shan Li, Lei Chen, Yu-Xing Peng, and Nong Xiao Journal of Computer Science and Technology, 2008, 23 (5 ): 780-791 . Abstract PDF(9812KB) ( 1792 ) Chinese Summary Multicast is essential for wireless sensor network (WSN) applications. Existing multicast protocols in WSNs are often designed in a P2P pattern, assuming small number of destination nodes and frequent changes in network topologies. In order to truly adopt multicast in WSNs, we propose a base-station model-based multicast, SenCast, to meet the general requirements of applications. SenCast is scalable and energy-efficient for large group communications in WSNs. Theoretical analysis shows that SenCast is able to approximate the Minimum Nonleaf Nodes (MNN) problem to a ratio of$\ln|R|(R\$ is the set of all destinations), the best known lowest bound. We evaluate our design through comprehensive simulations and prototype implementations on Mica2 motes. Experimental results demonstrate that SenCast outperforms previous multicast protocols including the most recent work uCast.
 Select Parallel Algorithm Core: A Novel IPSec Algorithm Engine for Both Exploiting Parallelism and Improving Scalability Dong-Nian Cheng, Yu-Xiang Hu, and Cai-Xia Liu Journal of Computer Science and Technology, 2008, 23 (5 ): 792-805 .  Abstract   PDF(598KB) ( 2179 )   Chinese Summary To deal with the challenges of both {\it computation-complexity} and {\it algorithm-scalability} posed to the design of an IPSec engine, we develop PAC (parallel algorithm core), called PAC, employed in an IPSec engine, which can meet requirements of both exploiting parallelism existing in IPSec packets and offering scalability in both the scales and types of cryptographic algorithms. With three kinds of parallelism and two kinds of transparency defined, a novel hierarchy of the specifically-designed parallel structure for PAC is presented, followed by corresponding mechanisms. With a simulation, the scalability of PAC is examined. For the purpose of performance evaluation, a {\it Quasi Birth-and-Death} (QBD) process is then established to model a simplified version of the proposed PAC. Performance evaluation of PAC in terms of two representative measures, throughput and mean packet waiting time, is numerically investigated. A comparison study is done on a simulation basis. Conclusions are finally drawn for providing a helpful guideline for both the design and implementation of our proposal.
 Select Uplink Scheduling for Supporting Real Time Voice Traffic in IEEE 802.16 Backhaul Networks Lizhong Dai and Dongmei Zhao Journal of Computer Science and Technology, 2008, 23 (5 ): 806-814 .  Abstract   PDF(476KB) ( 1656 )   Chinese Summary In this paper we propose simple enhancements to the bandwidth (BW) request messages in IEEE 802.16 for supporting real-time packet voice traffic. Three different BW request formats are proposed, each requiring a different amount of latency information about the buffered packets at the SS. On this basis, packet scheduling schemes are proposed for the BS to make resource allocations for real-time traffic. Our results show that the proposed BW request and scheduling schemes achieve significantly lower packet loss probability than the standard IEEE 802.16 BW request with round robin scheduling. The results further show that there is an optimum point about how much delay information the SS should report to the BS in order to best utilize the uplink resources while the SS provides satisfactory real-time performance for the voice traffic.
 Select Flood Avoidance Mechanisms for Bridged Resilient Packet Rings Pisai Setthawong and Surat Tanterdtid Journal of Computer Science and Technology, 2008, 23 (5 ): 815-824 .  Abstract   PDF(1803KB) ( 1252 )   Chinese Summary Resilient Packet Ring (RPR), or the Standard IEEE 802.17, is a new IP-based network technology proposed to replace SONET/SDH in metropolitan area networks. RPR is well-adapted to handle multimedia traffic and is efficient. However, when RPR networks are bridged, inter-ring packets, or packets with the destination on a remote RPR network other than on the source network, are flooded on the source and the destination networks, and also on the path of the intermediate networks between the source and the destination networks. This decreases the available bandwidth for other traffic in those networks and is inefficient. As a result, we propose two solutions based on topology discovery, global topology discovery (GTD) and enhanced topology discovery (ETD), that prevent the flooding of inter-ring packets. GTD enables the bridges to determine the next-hop bridge for each destination. ETD enables the source node to determine a default ringlet, so that packets reach the next-hop bridge without flooding the source network. The proposed solutions were analyzed and the overhead bandwidth and stabilization time were shown to be bounded. Simulations performed showed that the proposed solutions successfully avoid flooding and achieve optimal efficiency in the intermediate and destination networks, and in the source networks with one bridge.
 Select A Class of Key Predistribution Schemes Based on Orthogonal Arrays Jun-Wu Dong, Ding-Yi Pei, and Xue-Li Wang Journal of Computer Science and Technology, 2008, 23 (5 ): 825-831 .  Abstract   PDF(525KB) ( 2205 )   Chinese Summary Pairwise key establishment is a fundamental security service in sensor networks; it enables sensor nodes to communicate securely with each other using cryptographic techniques. In order to ensure this security, many approaches have been proposed recently. One of them is to use key predistribution schemes (KPSs) by means of combinatorial designs. In this paper, we use the Bush's construction of orthogonal arrays to present a class of key predistribution schemes for distributed sensor networks. The secure connectivity and resilience of the resulting sensor network are analyzed. This KPS constructed in our paper has some better properties than those of the existing schemes.
 Select A Provable Secure ID-Based Explicit Authenticated Key Agreement Protocol Without Random Oracles Hai-Bo Tian, Willy Susilo, Yang Ming, and Yu-Min Wang Journal of Computer Science and Technology, 2008, 23 (5 ): 832-842 .  Abstract   PDF(495KB) ( 2247 )   Chinese Summary In this paper, we present an identity-based {\it explicit authenticated} key agreement protocol that is provably secure without random oracles. The protocol employs a new method to isolate a session key from key confirmation keys so that there is no direct usage of hash functions in the protocol. The protocol is proved secure without random oracles in a variant of Bellare and Rogaway style model, an exception to current proof method in this style model in the ID-based setting. We believe that this key isolation method is novel and can be further studied for constructing more efficient protocols.
 Select Some Notes on Generalized Cyclotomic Sequences of Length pq Zhi-Xiong Chen and Sheng-Qiang Li Journal of Computer Science and Technology, 2008, 23 (5 ): 843-850 .  Abstract   PDF(665KB) ( 1643 )   Chinese Summary We review the constructions of two main kinds of generalized cyclotomic binary sequences with length {\it pq} (the product with two distinct primes). One is the White-generalized cyclotomic sequences, the other is the Ding-Helleseth(DH, for short)-generalized cyclotomic sequences. We present some new pseudo-random properties of DH-generalized cyclotomic sequences using the theory of character sums instead of the theory of cyclotomy, which is a conventional method for investigating generalized cyclotomic sequences.
 Select Palmprint Recognition by Applying Wavelet-Based Kernel PCA Murat Ekinci and Murat Aykut Journal of Computer Science and Technology, 2008, 23 (5 ): 851-861 .  Abstract   PDF(2940KB) ( 3428 )   Chinese Summary This paper presents a wavelet-based kernel Principal Component Analysis (PCA) method by integrating the Daubechies wavelet representation of palm images and the kernel PCA method for palmprint recognition. Kernel PCA is a technique for nonlinear dimension reduction of data with an underlying nonlinear spatial structure. The intensity values of the palmprint image are first normalized by using mean and standard deviation. The palmprint is then transformed into the wavelet domain to decompose palm images and the lowest resolution subband coefficients are chosen for palm representation. The kernel PCA method is then applied to extract non-linear features from the subband coefficients. Finally, similarity measurement is accomplished by using weighted Euclidean linear distance-based nearest neighbor classifier. Experimental results on PolyU Palmprint Databases demonstrate that the proposed approach achieves highly competitive performance with respect to the published palmprint recognition approaches.
 Select Free-Form Deformation with Rational DMS-Spline Volumes Gang Xu, Guo-Zhao Wang, and Xiao-Diao Chen Journal of Computer Science and Technology, 2008, 23 (5 ): 862-873 .  Abstract   PDF(8049KB) ( 1983 )   Chinese Summary In this paper, we propose a novel free-form deformation (FFD) technique, RDMS-FFD (Rational DMS-FFD), based on rational DMS-spline volumes. RDMS-FFD inherits some good properties of rational DMS-spline volumes and combines more deformation techniques than previous FFD methods in a consistent framework, such as local deformation, control lattice of arbitrary topology, smooth deformation, multiresolution deformation and direct manipulation of deformation. We first introduce the rational DMS-spline volume by directly generalizing the previous results related to DMS-splines. How to generate a tetrahedral domain that approximates the shape of the object to be deformed is also introduced in this paper. Unlike the traditional FFD techniques, we manipulate the vertices of the tetrahedral domain to achieve deformation results. Our system demonstrates that RDMS-FFD is powerful and intuitive in geometric modeling.
 Select Guiding Attention by Cooperative Cues KangWoo Lee Journal of Computer Science and Technology, 2008, 23 (5 ): 874-884 .  Abstract   PDF(15258KB) ( 1358 )   Chinese Summary A common assumption in visual attention is based on the rationale of limited capacity of information processing''. From this view point there is little consideration of how different information channels or modules are cooperating because cells in processing stages are forced to compete for the limited resource. To examine the mechanism behind the cooperative behavior of information channels, a computational model of selective attention is implemented based on two hypotheses. Unlike the traditional view of visual attention, the cooperative behavior is assumed to be a dynamic integration process between the bottom-up and top-down information. Furthermore, top-down information is assumed to provide a contextual cue during selection process and to guide the attentional allocation among many bottom-up candidates. The result from a series of simulation with still and video images showed some interesting properties that could not be explained by the competitive aspect of selective attention alone.
 Journal Online
 Just Accepted Archive Top Cited Papers Top 30 Most Read Paper Lists of Areas Surveys Special Issues
ScholarOne Manuscripts