9862925
Powers of Asteroidal Triple-free Graphs with Applications
An asteroidal triple is an independent set of three vertices in a graph such that every two of them are joined by a path avoiding the closed neighborhood of the third. Graphs without asteroidal triples are called AT-free graphs. In this paper, we show that every AT-free graph admits a vertex ordering that we call a 2-cocomparability ordering. The new suggested ordering generalizes the cocomparability ordering achievable for cocomparability graphs. According to the property of this ordering, we show that every proper power G (k ≥ 2) of an AT-free graph G is a cocomparability graph. Moreover, we demonstrate that our results can be exploited for algorithmic purposes on AT-free graphs.
34947079
On the powers of graphs with bounded asteroidal number
Abstract For an undirected graph G =( V , E ), the kth power G k is the graph with the same vertex set as G such that two vertices are adjacent in G k if and only if their distance in G is at most k. A set of vertices A ⊆ V is an asteroidal set if for every vertex a ∈ A , the set A ⧹{ a } is contained in one connected component of G − N G [ a ], where N G [ a ] is the closed neighborhood of a in G. The asteroidal number of a graph G is the maximum cardinality of an asteroidal set in G. The class of graphs with asteroidal number at most s is denoted by A (s) . In this paper, we show that if G k ∈ A (s) for s ⩾2, then so is G k +1 . This generalizes a previous result for the family of AT-free graphs. Moreover, we consider the forbidden configurations for the powers of graphs with bounded asteroidal number. Based on these forbidden configurations, we show that every proper power of AT-free graphs is perfect.
13312657
Feedback vertex sets in star graphs
In a graph G = (V, E), a subset F ⊂ V(G) is a feedback vertex set of G if the subgraph induced by V(G) \ F is acyclic. In this paper, we propose an algorithm for finding a small feedback vertex set of a star graph. Indeed, our algorithm can derive an upper bound to the size of the feedback vertex set for star graphs. Also by applying the properties of regular graphs, a lower bound can easily be achieved for star graphs.
29352440
Induced matchings in asteroidal triple-free graphs
An induced matching M of a graph G is a set of pairwise nonadjacent edges such that no two edges of M are joined by an edge in G. The problem of finding a maximum induced matching is known to be NP-hard even for bipartite graphs of maximum degree four. In this paper, we study the maximum induced matching problem on classes of graphs related to AT-free graphs. We first define a wider class of graphs called the line-asteroidal triple-free (LAT-free) graphs which contains AT-free graphs as a subclass. By examining the square of line graph of LAT-free graphs, we give a characterization of them and apply this for showing that the maximum induced matching problem and a generalization, called the maximum δ-separated matching problem, on LAT-free graphs can be solved in polynomial time. In fact, our result can be extended to the classes of graphs with bounded asteroidal index. Next, we propose a linear-time algorithm for finding a maximum induced matching in a bipartite permutation (bipartite AT-free) graph using the greedy approach. Moreover, we show that using the same technique the minimum chain subgraph cover problem on bipartite permutation graphs can be solved with the same time complexity.
205287010
Quality of service support in IEEE 802.11 wireless ad hoc networks
Abstract Supporting Quality of Service (QoS) in wireless networks is a challenging problem. The IEEE 802.11 LAN standard was developed primarily for elastic data applications. In order to support the transmission of real-time data, a polling-based scheme called the point coordination function (PCF) was introduced in IEEE 802.11. However, PCF was not able to meet the desired and practical service differentiation requirements to fulfill the need of real-time data. Therefore, Task Group E of the IEEE 802.11 working group released several IEEE 802.11e drafts, whose main task is to support QoS in IEEE 802.11 LANs. The polling scheme of PCF is extended in IEEE 802.11e into the more complex hybrid coordination function (HCF). We found that HCF has several performance issues that may affect its anticipated performance. In this paper, we address these issues and propose a QoS enhancement over PCF, called enhanced PCF (EPCF) that enables Wireless LAN to send a combination of voice, data and isochronous data packets using the current IEEE 802.11 PCF. First, we compare the performance of the proposed model (EPCF) with the HCF function of the IEEE 802.11e through simulation. Second, we extend the proposed model (EPCF) to work in a multihop wireless ad hoc mode and present the advantages and limitations in this case. Simulation results demonstrate an enhanced performance of our scheme over the legacy PCF and a comparable performance to the IEEE 802.11e HCF in terms of the average delay and system throughput. However, EPCF is much simpler than HCF, provides flow differentiation, and is easy to implement in the current IEEE 802.11 standard.
1050294
Towards pairing Java applications on SMT processors
This paper investigates various issues of pairing Java applications for multithreaded execution on Intel's hyper-threading Pentium 4 processor. We first quantify the overall performance of multiprogrammed Java applications using a metric called combined speedup. Using the performance counters provided by the Pentium 4, we then quantitatively evaluate the performance of underneath micro-architecture components and their implications to the combined speedup. A statistical model is proposed to analyze the collected data. This novel approach reveals that trace cache is the major factor determining the pairing performance. In particular, we find that the trace cache miss rates of Java applications can be utilized to predict the combined speedups. Three new scheduling strategies are proposed based on these observations and then evaluated. The experimental results show that the proposed strategies have better performance than the conventional round-robin scheduling scheme. Overall, our best strategy enables a reduction in execution time of 10.5% over the serial execution, comparing with a reduction of 5.92% achieved by the round-robin scheduling. The improvement will be increasingly significant on future SMT processors.
38166516
A Sufficient Condition for Quasi-Claw-Free Hamiltonian Graphs
There are several well-known and important hamiltonian results for claw-free graphs but only a few are concerned with quasi-claw-free graphs. In this note, we provide a new sufficient condition for quasi-claw-free hamiltonian graphs.
7532286
Finding recent frequent itemsets adaptively over online data streams
A data stream is a massive unbounded sequence of data elements continuously generated at a rapid rate. Consequently, the knowledge embedded in a data stream is more likely to be changed as time goes by. Identifying the recent change of a data stream, specially for an online data stream, can provide valuable information for the analysis of the data stream. In addition, monitoring the continuous variation of a data stream enables to find the gradual change of embedded knowledge. However, most of mining algorithms over a data stream do not differentiate the information of recently generated transactions from the obsolete information of old transactions which may be no longer useful or possibly invalid at present. This paper proposes a data mining method for finding recent frequent itemsets adaptively over an online data stream. The effect of old transactions on the mining result of the data steam is diminished by decaying the old occurrences of each itemset as time goes by. Furthermore, several optimization techniques are devised to minimize processing time as well as main memory usage. Finally, the proposed method is analyzed by a series of experiments.
17498259
estWin: adaptively monitoring the recent change of frequent itemsets over online data streams
Knowledge embedded in a data stream is likely to be changed as time goes by. Consequently, identifying the recent change of the knowledge quickly can provide valuable information for the analysis of the data stream. However, most of mining algorithms or frequency approximation algorithms for a data stream do not able to extract the recent change of information in a data stream adaptively. This paper proposes a sliding window-based method that finds recently frequent itemsets over an online data stream adaptively. The size of a window defines a desired life-time of the information in a newly generated transaction. Consequently, only recently generated transactions in the range of the window are considered to find the frequent itemsets of a data stream.