6641485
On total covers of graphs
A total cover of a graph G is a subset of V(G)∪E(G) which covers all elements of V(G)∪E(G). The total covering number α2(G) of a graph G is the minimum cardinality of a total cover in G. In [1], it is proven that α2(G)⩽[n2] for a connected graph G of order n. Here we consider the extremal case and give some properties of connected graphs which have a total covering number [n2]. We prove that such a graph with even order has a 1-factor and such a graph with odd order is factor-critical.
11520313
Linear Vertex Arboricity, Independence Number and Clique Cover Number
The linear vertex-arboricity of a graph G is defined to the minimum number of subsets into which the vertex-set G can be partitioned so that every subset induces a linear forest. In this paper, we give the upper and lower bounds for sum and product of linear vertex-arboricity with independence number and with clique cover number respectively. All of these bounds are sharp.
206571042
An Upper Bound for the Independent Domination Number
Let G be a simple graph of order n and minimum degree ?. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. In this paper, we show that i(G)?n+2??2n?. Thus a conjecture of Favaron is settled in the affirmative.
22378712
Optimal management of cross-trained workers in services with negligible switching costs
In this paper we consider a retail service facility with cross-trained workers who can switch between the front room and the back room depending on the size of the queue in the front room. Two problems are presented. In the first problem, given a fixed number of cross-trained workers the objective is to find optimal switching points so that the expected customer waiting time is minimized subject to a back room service level constraint. In the second problem the number of workers is also a decision variable and the objective is to minimize it subject to both front room and back room service level constraints. The paper includes an analysis of the model and based on it several heuristics are suggested. Computational analysis with the recommended heuristics is presented and comparison to optimal solutions derived by complete enumeration shows excellent results.
17750098
Lineage Path Integration for Phylogenetic Resources
With the increase of genome and proteome data, phylogenetic information and phylogenetic analysis tools are increasing greatly in current biological repositories. First, many repositories allow users to browse information about species through taxonomic tools. These tools present the species with its lineage path and links to the various types of information the repository provides about the species. Second, some multiple sequence alignment tools offer users basic phylogenetic data through applying basic reconstruction algorithms to the alignment. With the availability of this information in multiple locations, integrated tools are needed to allow the user to compare this data. This paper presents data integration research on lineage paths using the BIO-AJAX framework. It introduces BIO-AJAX for Lineage Paths, a tool that integrates lineage path information for NCBI Taxonomy Database [1] and the Integrated Taxonomic Information System (ITIS)[6].
21957858
Algorithms for Approximate Graph Matching
Abstract Labeled graphs are graphs in which each node and edge has a label. The distance between two labeled graphs is considered to be the weighted sum of the costs of edit operations (insert, delete, and relabel the nodes and edges) to transform one graph to the other. The paper considers two variants of the approximate graph matching problem (AGM): Given a pattern graph P and a data graph D : 1. 1. What is the distance between P and D ? 2. 2. What is the minimum distance between P and D when subgraphs can be freely removed from D ? We first show that no efficient algorithm can solve either variant of the AGM unless P = NP. Then we present several heuristic algorithms leading to approximate solutions. The heuristics are based on probabilistic hill climbing and maximum flow techniques. Our experimental results involving the comparison of real and simulated data demonstrate the good performance of the algorithms presented.
6516220
Resource-Constrained Workflow Modeling
Business processes are often constrained by resource availability. This is particularly true in an emergency response system where large quantity of resources, including emergency responders, ambulances, fire trucks, medications, food, clothing, etc., are required. In our previous work, we introduced WIFA model to meet the needs of incident command systems workflow modeling and analysis. In this paper, we extend WIFA to take resources into account when modeling and enacting workflows. A formal resource-constrained workflow model is defined and the state transitions rules are established to support workflow analysis. An example is given to illustrate the use of the model.
45865876
Graph theoretic characterization and reliability of the generalized Boolean n-cube network
In this paper, a general class of Boolean n-cube structures is investigated. The interconnection is based on a mixed radix number system which results in a variety of generalized Boolean n-cube structures for a given number of processors N = x·2y, where x and y are positive integers. A number of interesting properties of the network are revealed. By a constructive method, the node connectivity of this network is found. Finally, we show that the graph is super-λ and is an optimal reliable structure for interconnection networks.