36993971
Distance-hereditary graphs are clique-perfect
In this paper, we show that the clique-transversal number @t"C(G) and the clique-independence number @a"C(G) are equal for any distance-hereditary graph G. As a byproduct of proving that @t"C(G)[email protected]"C(G), we give a linear-time algorithm to find a minimum clique-transversal set and a maximum clique-independent set simultaneously for distance-hereditary graphs.
10016971
Improved bottleneck domination algorithms
W.C.K. Yen introduced BOTTLENECK DOMINATION and BOTTLENECK INDEPENDENT DOMINATION. He presented an O(n log n + m)- time algorithm to compute a minimum bottleneck dominating set. He also obtained that the BOTTLENECK INDEPENDENT DOMINATING SET problem is NP-complete, even when restricted to planar graphs.We present simple linear time algorithms for the BOTTLENECK DOMINATING SET and the BOTTLENECK TOTAL DOMINATING SET problem. Furthermore, we give polynomial time algorithms (most of them with linear time-complexities) for the BOTTLENECK INDEPENDENT DOMINATING SET problem on the following graph classes: AT-free graphs, chordal graphs, split graphs, permutation graphs, graphs of bounded treewidth, and graphs of clique-width at most k with a given k-expression.
9024709
Time-Constrained Service on Air
Data broadcasting is an efficient and highly scalable technique for delivering data to mobile clients in wireless environments. In this paper, we study the problem of scheduling broadcast data that are with an expected time within which the client is expecting to receive the data item. We analyze the problem and derive the minimum number of broadcast channels required for such a task. Also, we discuss the problems when the number of available channels is not enough. We propose novel solutions for both of the cases and the performance study indicates that our method is much better than the previous ones and performs very close to optimal
18796888
Design and Performance Evaluation of Broadcast Algorithms for Time-Constrained Data Retrieval
We refer "time-constrained services" to those requests that have to be replied to within a certain client-expected time duration. If the answer cannot reach the client within this expected time, the value of the information may seriously degrade or even become useless. On-demand channels may not be able to handle all time-constrained services without degrading the performance. How to handle these services in broadcast channels becomes crucial to balance the load of wireless systems. In this paper, we study this problem and find the minimum number of broadcast channels required for such a task. Also, we propose solutions for this problem when the available channels are insufficient. Our performance result reveals that only a moderate number of channels is required to promote these time-constrained services
32239506
An intelligent fuzzy agent for meeting scheduling decision support system
Abstract An Intelligent Fuzzy Agent for Meeting Scheduling Decision Support System is proposed in this paper. The proposed Intelligent Fuzzy Agent including Meeting Negotiation Agent, Fuzzy Inference Agent and Genetic Learning Agent can search and decide the suitable meeting time for the specified meeting in an organization. When a meeting host requests a meeting, the Meeting Negotiation Agent immediately sends the invitees’ names to Meeting Scheduling Decision Support System for retrieving their schedules from Group Calendar Data Base, then Meeting Scheduling Decision Support System will compute the possible meeting time and respond the results to Meeting Negotiation Agent. Moreover, the Fuzzy Inference Agent infers the adequate meeting time based on the information provided by Meeting Negotiation Agent and Personalized Knowledge Base, and sends the computing result back to Meeting Scheduling Decision Support System. The meeting host will decide the final meeting time based on Meeting Scheduling Decision Support System and announce the meeting information by various devices including PDA, WAP, FAX, or E-mail. Furthermore, the invitees’ decisions for attending the meeting or not will be stored into Meeting Information Knowledge Base, then the Genetic Learning Agent will adjust the Personalized Knowledge Base for the next meeting. By the experimental results, the proposed Intelligent Fuzzy Agent can work efficiently and effectively for Meeting Scheduling Decision Support System.
2862791
A data delivery strategy in ubiquitous computing systems
Browsing Web pages through wireless devices will become more and more popular in the near future. However, accessing a large chunk of Web data incurs a great amount of access latency while a mobile user migrates across cells. This paper investigates this problem and proposes an effective way of delivering such data to a mobile user in a ubiquitous computing system. Our data delivery (/spl Dscr//sup 2/) strategy is based on the dynamic programming skill needed to pre-assign the user-requested data on the possible cells to be visited in order to reduce the access latency. We first design an encoding method for the cells and then derive the properties of the encoding scheme. These properties are then used in our algorithm to deliver the data. Finally, experiments are conducted to demonstrate the feasibility and efficiency of the proposed method.
5313535
Variable Length Genomes for Evolutionary Algorithms
A variable length genome has been developed to search variable dimensionality/complexity spaces efficiently. A simple proof of concept experiment shows the utility of such a representation.