26869429
Orthogonal (g, f)-factorizations in graphs
Abstract Let G be a graph and let F = F 1 , F 2 , …, F m and H be a factorization and a subgraph of G, respectively. If H has exactly one edge in common with F i for all i, 1 ⩽ i ⩽ m , then we say that F is orthogonal to H . Let g and f be two integer-valued functions defined on V ( G ) such that g ( x ) ⩽ f ( x ) for every x ϵ V ( G ). In this paper it is proved that for any m -matching M of an ( mg + m − 1, mf − m + 1)-graph G, there exists a ( g , f )-factorization of G orthogonal to M .
9736348
Some Problems on Factorizations with Constraints in Bipartite Graphs
Let G = (X, Y, E(G)) be a bipartite graph with vertex set V(G) = X ∪ Y and edge set E(G) and let g and f be two non-negative integer-valued functions defined on V(G) such that g(x) ≤ f(x) for each x ∈ V(G). A (g, f)-factor of G is a spanning subgraph F of G such that g(x) ≤ dF(x) ≤ f(x) for each x ∈ V(F); a (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. In this paper it is proved that every bipartite (mg + m - 1, mf - m + 1)-graph has (g, f)-factorizations randomly k-orthogonal to any given subgraph with km edges if k ≤ g(x) for any x ∈ V(G) and has a (g, f)-factorization k-orthogonal to any given subgraph with km edges if k - 1 ≤ g(x) for any x ∈ V(G) and that every bipartite (mg, m f)-graph has a (g, f)-factorization orthogonal to any given m-star if 0 ≤ g(x) ≤ f(x) for any x ∈ V(G). Furthermore, it is shown that there are polynomial algorithms for finding the desired factorizations and the results in this paper are in some sense best possible.
7451094
Orthogonal (g, f)-factorizations in networks
Let G = (V,E) be a graph and let g and f be two integer-valued functions defined on V such that k ≤ g(x) ≤ f(x) for all x ∈ V . Let H1,H2, · · · ,Hk be subgraphs of G such that |E(Hi)| = m, 1 ≤ i ≤ k, and V (Hi) ∩ V (Hj) = ∅ when i 6= j. In this paper it is proved that every (mg + m − 1,mf −m + 1)-graph G has a (g, f)-factorization orthogonal to Hi for i = 1, 2, · · · , k and shown that there are polynomial-time algorithms to find the desired (g, f)-factorizations.
35387631
A lower bound on connectivities of matroid base graphs
Abstract The connectivity of a graph G and the corank of a matroid M are denoted by κ ( G ) and ϱ , respectively. It is shown that if a graph G is the base graph of a simple matroid M , then κ ( G )⩾2 ϱ and the lower bound of 2 ϱ is best possible.
5451258
Toughness and Perfect Matchings in Graphs
1047063
Generalization of matching extensions in graphs
Abstract Let G be a graph with vertex set V(G) . Let n, k and d be non-negative integers such that n+2k+d⩽|V(G)|−2 and |V(G)|−n−d is even. A matching which covers exactly |V(G)|−d vertices of G is called a defect - d matching of G . If when deleting any n vertices of G the remaining subgraph contains a matching of k edges and every k -matching can be extended to a defect- d matching, then G is called a (n,k,d) - graph . In this paper a characterization of (n,k,d) -graphs is given and several properties (such as connectivity, minimum degree, hierarchy, etc.) of (n,k,d) -graphs are investigated.
195706995
A Mobility-Aware Dynamic Database Caching Scheme for Wireless Mobile Computing and Communications
This paper describes a mobility-aware dynamic database caching scheme for wireless mobile computing and communications. A mobile-floating agent scheme is proposed, in which caching techniques are cognizant of the mobile nature of mobile users and the location-sensitive nature of mobile systems. The mobile-floating agent maintains a second class cache in the fixed network and employs Barbara’s “invalidation reports broadcasting” cache consistency strategies to maintain a dynamic cache consistent with the first class cache in the mobile client. The “invalidation reports broadcasting” scheme is combined with knowledge of the mobility behavior of each individual mobile user and broadcasts of invalidation reports only occur within the user’s mobility area. The evaluation results show that, for a large system (200 cells), this scheme can reduce the system cost by more than 87%, for even highly mobile users, compared with a fully replicated database system.
6438586
A mobile virtual-distributed system architecture for supporting wireless mobile computing and communications
This paper describes a novel mobile virtual-distrubuted system architecture for supporting global mobile computing and communications. the principal contribution of this paper is to innovatively apply virtual memory concepts to mobile systems by deploying mobile-floating agents to de-couple services and resources from the underlying network and allow them to move around following their mobile users. The mobile-floating agents maintain data structures associated with a mobile user. By combining the mobile-floating agent functions with a predictive mobility management algorithm and location-aware caching and prefetching, services and user data structure are pre-connected and pre-assigned at the locations to which the user is moving. Thus, the users can maintain their data structures or immediately receive service with virtually the same efficiency as at the previous location.
11364817
A class of mobile motion prediction algorithms for wireless mobile computing and communications
This paper describes a class of novel mobile motion prediction algorithms for supporting global mobile data accessing. Traditionally, mobility and routing management includes functions to passively keep track of the location of the users/terminals and to maintain connections to the terminals belonging to the system. To maintain uninterrupted high-quality service for distributed applications, it is important that a mobile system be more intelligent and can anticipate the change of the location of its user. We propose an aggressive mobility and routing management scheme, called predictive mobility management. A class of mobile motion prediction algorithms predicts the “future” location of a mobile user according to the user's movement history, i.e., previous movement patterns. By combining this scheme with mobility agent functions, the service and user routing data are actually pre-connected and pre-assigned at the locations to which the user is moving. Thus, the user can immediately receive service or data with virtually the same efficiency as at the previous location, i.e., without encountering a large “data structure handover” delay before service or data is available.
232914
Active and real-time functionalities for electronic brokerage design
In this position paper, we discuss an architecture for developing next generation electronic brokerages using active and real-time functionalities. These electronic brokerages support timeliness requirements and allow users to express complex preferences. User preferences can be conveniently captured as event-condition-action (ECA) rules. The design allows pro-active monitoring of user preferences and execution of actions in a timely manner. A proof-of-concept prototype is implemented using Java in the context of online trading. The prototype consists of three major components: rule validator, active rule manager and event monitor.
8336028
Evaluation and optimization of clustering in gene expression data analysis
MOTIVATION
A measurement of cluster quality is needed to choose potential clusters of genes that contain biologically relevant patterns of gene expression. This is strongly desirable when a large number of gene expression profiles have to be analyzed and proper clusters of genes need to be identified for further analysis, such as the search for meaningful patterns, identification of gene functions or gene response analysis.


RESULTS
We propose a new cluster quality method, called stability, by which unsupervised learning of gene expression data can be performed efficiently. The method takes into account a cluster's stability on partition. We evaluate this method and demonstrate its performance using four independent, real gene expression and three simulated datasets. We demonstrate that our method outperforms other techniques listed in the literature. The method has applications in evaluating clustering validity as well as identifying stable clusters.


AVAILABILITY
Please contact the first author.