7791840
Pseudo-Hamiltonian-connected graphs
Abstract Given a graph G and a positive integer k , denote by G[k] the graph obtained from G by replacing each vertex of G with an independent set of size k . A graph G is called pseudo- k Hamiltonian-connected if G[k] is Hamiltonian-connected, i.e., every two distinct vertices of G[k] are connected by a Hamiltonian path. A graph G is called pseudo Hamiltonian-connected if it is pseudo- k Hamiltonian-connected for some positive integer k . This paper proves that a graph G is pseudo-Hamiltonian-connected if and only if for every non-empty proper subset X of V(G) , |N(X)|>|X| . The proof of the characterization also provides a polynomial-time algorithm that decides whether or not a given graph is pseudo-Hamiltonian-connected. The characterization of pseudo-Hamiltonian-connected graphs also answers a question of Richard Nowakowski, which motivated this paper.
8130739
Homomorphisms to oriented cycles
We discuss the existence of homomorphisms to oriented cycles and give, for a special class of cyclesC, a characterization of those digraphs that admit, a homomorphism toC. Our result can be used to prove the multiplicativity of a certain class of oriented cycles, (and thus complete the characterization of multiplicative oriented cycles), as well as to prove the membership of the corresponding decision problem in the classNPϒcoNP. We also mention a conjecture on the existence of homomorphisms to arbitrary oriented cycles.
34675136
Density of the circular chromatic numbers of series-parallel graphs
41218825
Relaxed game chromatic number of graphs
This paper discusses a coloring game on graphs. Let k, d be non-negative integers and C a set of k colors. Two persons, Alice and Bob, alternately color the vertices of G with colors from C, with Alice having the first move. A color i is legal for an uncolored vertex x if by coloring x with color i, the subgraph of G induced by those vertices of color i has maximum degree at most d. Each move of Alice or Bob colors an uncolored vertex with a legal color. The game is over if either all vertices are colored, or no more vertices can be colored with a legal color. Alice's goal is to produce a legal coloring which colors all the vertices of G, and Bob's goal is to prevent this from happening. We shall prove that if G is a forest, then for k = 3, d ≥ 1, Alice has a winning strategy. If G is an outerplanar graph, then for k = 6 and d ≥ 1, Alice has a winning strategy.
36146387
On Hedetniemi's conjecture and the colour template scheme
Hedetniemi's conjecture states that the chromatic number of a product of graphs is the minimum of the chromatic numbers of the factors. El-Zahar and Sauer (Combinatorica 5 (1985) 121) have shown that the chromatic number of a product of 4-chromatic graphs is 4. In this paper, we investigate to which extent their methods can be adapted to the case of 5-chromatic graphs. Our main result is that if G and H are connected graphs of chromatic number at least 5 that both contain odd wheels as subgraphs, then their product also has chromatic number at least 5. However, we also provide counterexamples to the El-Zahar and Sauer conjecture on the structure of n-chromatic subgraphs of products of n-chromatic graphs. This implies that the method of El-Zahar and Sauer will not be sufficient to prove all cases of Hedetniemi's conjecture for chromatic numbers larger than 4.
46567686
The level of nonmultiplicativity of graphs
We introduce a parameter called the level of nonmultiplicativity of a graph, which is related to Hedetniemi's conjecture. We show that this parameter is equal to the number of factors in a factorization of the graph into a product of multiplicative graphs. Apart from the known multiplicative graphs, no graph is known to have a finite level of nonmultiplicativity. We show that the countably infinite complete graph KN0 has an infinite level of nonmultiplicativity and that there exist Kneser graphs with arbitrarily high levels of nonmultiplicativity.
9200586
Scalable Inductive Learning on Partitioned Data
With the rapid advancement of information technology, scalability has become a necessity for learning algorithms to deal with large, real-world data repositories. In this paper, scalability is accomplished through a data reduction technique, which partitions a large data set into subsets, applies a learning algorithm on each subset sequentially or concurrently, and then integrates the learned results. Five strategies to achieve scalability (Rule-Example Conversion, Rule Weighting, Iteration, Good Rule Selection, and Data Dependent Rule Selection) are identified and seven corresponding scalable schemes are designed and developed. A substantial number of experiments have been performed to evaluate these schemes. Experimental results demonstrate that through data reduction some of our schemes can effectively generate accurate classifiers from weak classifiers generated from data subsets. Furthermore, our schemes require significantly less training time than that of generating a global classifier.
1251013
Congestion-aware rate allocation for multipath video streaming over ad hoc wireless networks
For multipath video streaming over ad hoc wireless networks, received video quality is influenced by both the encoder performance and the delayed packet arrivals due to limited bandwidth. We propose a rate allocation scheme to optimize the expected received video quality based on simple models of encoder rate-distortion performance and network rate-congestion tradeoffs. Given the embedded bit-streams of a group of video frames and the cross traffic condition on a given set of paths, a gradient descent method is used to determine the amount of bits to be transmitted over the multiple paths for each frame. Two rate allocation strategies, layered representation and partial repetition are also investigated. Simulation results of video streaming over a 15-node wireless ad hoc network demonstrates the benefit of performing rate allocation optimization over a simple heuristic scheme. It is also shown that while layered representation is more efficient for mild delay constraints, partial repetition is more robust against packet losses.
205872736
Flatness tolerance evaluation: an approximate minimum zone solution
Abstract This paper is concerned with the problem of flatness tolerance evaluation. First, we introduce the concepts of width and inner radius of point sets, and establish the equivalence between the width of a point set and the inner radius of the convex hull of the self-difference of the set. On this basis, we present an algorithm for calculating the exact minimum zone tolerance of flatness. Second, we prove that an approximation of the inner radius of a convex set can be obtained from the inner radius of the set in fixed direction. On this basis, we present an algorithm for calculating the ‘almost exact’ minimum zone solution. This algorithm is implemented by solving a single linear programming problem, of which the computational complexity is O ( n ). Numerical examples are given to validate the proposed algorithms.
14899560
Dealing with Predictive-but-Unpredictable Attributes in Noisy Data Sources
Attribute noise can affect classification learning. Previous work in handling attribute noise has focused on those predictable attributes that can be predicted by the class and other attributes. However, attributes can often be predictive but unpredictable. Being predictive, they are essential to classification learning and it is important to handle their noise. Being unpredictable, they require strategies different from those of predictable attributes. This paper presents a study on identifying, cleansing and measuring noise for predictive-but-unpredictable attributes. New strategies are accordingly proposed. Both theoretical analysis and empirical evidence suggest that these strategies are more effective and more efficient than previous alternatives.
12029215
Multiuser Detection and Channel Estimation in MIMO OFDM Systems via Blind Source Separation
This paper proposes a blind multiuser detection and channel estimation method for multiple-input multiple-output (MIMO) orthogonal frequency-division multiplexing (OFDM) systems based on blind source separation (BSS). Using multiple antennas for transmission and reception the multiuser detection problem can be cast as a BSS problem of linear instantaneous mixtures. The proposed method uses BSS in each subcarrier to detect the user signals. The source order and scaling indeterminacies inherent to BSS methods are overcome by exploiting the cross correlation between the subcarriers introduced by convolutional encoding. Additionally, the method provides an estimate of the channels. It is shown that this method provides significant performance enhancement over previous work.