16940810
Vertex and Tree Arboricities of Graphs
This paper studies the following variations of arboricity of graphs. The vertex (respectively, tree) arboricity of a graph G is the minimum number va(G) (respectively, ta(G)) of subsets into which the vertices of G can be partitioned so that each subset induces a forest (respectively, tree). This paper studies the vertex and the tree arboricities on various classes of graphs for exact values, algorithms, bounds, hamiltonicity and NP-completeness. The graphs investigated in this paper include block-cactus graphs, series-parallel graphs, cographs and planar graphs.
198001
Proper interval graphs and the guard problem
This paper is a study of the hamiltonicity of proper interval graphs with applications to the guard problem in spiral polygons. We prove that proper interval graphs with ?2 vertices have hamiltonian paths, those with ?3 vertices have hamiltonian cycles, and those with ?4 vertices are hamiltonian-connected if and only if they are, respectively, 1-, 2-, or 3-connected. We also study the guard problem in spiral polygons by connecting the class of nontrivial connected proper interval graphs with the class of stick-intersection graphs of spiral polygons.
28223559
Constructions of point-colour-symmetric graphs
Throuhout this paper, we shall restrict ourselves to finite graphs G which are undirected and line-coloured. For any points x, y in G, we shall write x y to mean that x and y are adjacent and by x w1 y to mean that x y and the colour of the line joining x and y is i. Also, we shall denote the line joining x and y by Xy; the colour of Xy by c(xy); and the set {c(Xy)l x y in Gl by C(G). Let G and H be (undirected, line-coloured) graphs. A one to one mapping ffrom G onto His called an isomorphism if the following two conditions are satisfied:
15331077
Precoded V-BLAST for ISI MIMO channels
The V-BLAST (vertical Bell labs layered space-time) system is one of the MIMO systems designed to achieve a good multiplexing gain. In the recent literature, a V-BLAST precoder has been added in the transmitter which exploits channel information. This precoder forces each symbol stream to have identical MSE (mean square error). It can be viewed as an alternative to the bitloading method. In this paper, this precoded V-BLAST is extended to the case of ISI MIMO channels. Both the FIR and OFDM types of transceivers are derived
16272778
The Maximum Partition Matching Problem with Applications
Let ${\cal S} = {C1, C2, . . . , Ck}$ be a collection of pairwise disjoint subsets of U = { 1, 2, . . . , n} such that $\bigcup_{i = 1}^k Ci = U. A partition matching of $\cal S$ consists of two subsets {a1, . . . , am} and {b1, . . ., bm} 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 ai is contained in a subset in the collection ${\cal A}_i$ and bi 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.
31774377
Factors in graphs with odd-cycle property
Abstract We present some conditions for the existence of a ( g , f )-factor or a ( g , f )-parity factor in a graph G with the odd-cycle property that any two odd cycles of G either have a vertex in common or are joined by an edge.
21143930
An I/O Optimal and Scalable Skyline Query Algorithm
Given a set of d-dimensional points, skyline query returns the points that are not dominated by any other point on all dimensions. Currently, BBS (branch-and-bound skyline) is the most efficient skyline processing method over static data in a centralized setting. Although BBS has some desirable features (e.g., I/O optimal and flexibility), it requires large main-memory consumption. In this paper, we present an improved skyline computation algorithm based on best-first nearest neighbor search, called IBBS, which captures the optimal I/O and less memory space (i.e., IBBS visits and stores only those entries that contribute to the final skyline). Its core enables several effective pruning strategies to discard non-qualifying entries. Extensive experimental evaluations show that IBBS outperforms BBS in both scalability and efficiency for most cases, especially in low dimensions.