An $$O(|E(G)|^2)$$ algorithm for recognizing Pfaffian graphs of a type of bipartite graphs

A graph \(G=(V,E)\) with even number vertices is called Pfaffian if it has a Pfaffian orientation, namely it admits an orientation such that the number of edges of any M-alternating cycle which have the same direction as the traversal direction is odd for some perfect matching M of the graph G. In this paper, we obtain a necessary and sufficient condition of Pfaffian graphs in a type of bipartite graphs. Then, we design an \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs in this class and constructs a Pfaffian orientation if the graph is Pfaffian. The results improve and generalize some known results.     

An algorithm for finding a representation of a subtree distance

Generalizing the concept of tree metric, Hirai (Ann Combinatorics 10:111–128, 2006) introduced the concept of subtree distance. A nonnegative-valued mapping \(d:X\times X \rightarrow \mathbb {R}_+\) is called a subtree distance if there exist a weighted tree T and a family \(\{T_x\mid x \in X\}\) of subtrees of T indexed by the elements in X such that \(d(x,y)=d_T(T_x,T_y)\), where \(d_T(T_x,T_y)\ge 0\) is the distance between \(T_x\) and \(T_y\) in T. Hirai (2006) provided a characterization of subtree distances that corresponds to Buneman’s (J Comb Theory, Series B 17:48–50, 1974) four-point condition for tree metrics. Using this characterization, we can decide whether or not a given mapping is a subtree distance in O\((n^4)\) time. In this paper, we show an O\((n^3)\) time algorithm that finds a representation of a given subtree distance. This results in an O\((n^3)\) time algorithm for deciding whether a given mapping is a subtree distance.     

$$(\alpha , \tau )$$-Monitoring for event detection in wireless sensor networks

Detecting abnormal events is one of the fundamental issues in wireless sensor networks (WSNs). In this paper, we investigate \((\alpha ,\tau )\)-monitoring in WSNs. For a given monitored threshold \(\alpha \), we prove that (i) the tight upper bound of \(\Pr [{S(t)} \ge \alpha ]\) is \(O\left( {\exp \left\{ { - n\ell \left( {\frac{\alpha }{{nsup}},\frac{{\mu (t)}}{{nsup}}} \right) } \right\} } \right) \), if \(\mu (t) < \alpha \); and (ii) the tight upper bound of \(\Pr [{S(t)} \le \alpha ]\) is \(O\left( {\exp \left\{ { - n\ell \left( {\frac{\alpha }{{nsup}},\frac{{\mu (t)}}{{nsup}}} \right) } \right\} } \right) \), if \(\mu (t) > \alpha \), where \(\Pr [X]\) is the probability of random event \(X,\, S(t)\) is the sum of the monitored area at time \(t,\, n\) is the number of the sensor nodes, \(sup\) is the upper bound of sensed data, \( \mu (t)\) is the expectation of \(S(t)\), and \(\ell ({x_1},{x_2}) = {x_1}\ln \left( {\frac{{{x_1}}}{{{x_2}}}} \right) + (1 - {x_1})\ln \left( {\frac{{1 - {x_1}}}{{1 - {x_2}}}} \right) \). An instant \((\alpha ,\tau )\)-monitoring scheme is then developed based on the upper bound. Moreover, approximate continuous \((\alpha , \tau )\)-monitoring is investigated. We prove that the probability of false negative alarm is \(\delta \), if the sample size is Open image in new window for a given precision requirement, where Open image in new window is the Open image in new window fractile of a standard normal distribution. Finally, the performance of the proposed algorithms is validated through experiments.     

The $$(k,\ell )$$-proper index of graphs

A tree T in an edge-colored graph is called a proper tree if no two adjacent edges of T receive the same color. Let G be a connected graph of order n and k be an integer with \(2\le k \le n\). For \(S\subseteq V(G)\) and \(|S| \ge 2\), an S-tree is a tree containing the vertices of S in G. A set \(\{T_1,T_2,\ldots ,T_\ell \}\) of S-trees is called internally disjoint if \(E(T_i)\cap E(T_j)=\emptyset \) and \(V(T_i)\cap V(T_j)=S\) for \(1\le i\ne j\le \ell \). For a set S of k vertices of G, the maximum number of internally disjoint S-trees in G is denoted by \(\kappa (S)\). The k-connectivity \(\kappa _k(G)\) of G is defined by \(\kappa _k(G)=\min \{\kappa (S)\mid S\) is a k-subset of \(V(G)\}\). For a connected graph G of order n and for two integers k and \(\ell \) with \(2\le k\le n\) and \(1\le \ell \le \kappa _k(G)\), the \((k,\ell )\)-proper index \(px_{k,\ell }(G)\) of G is the minimum number of colors that are required in an edge-coloring of G such that for every k-subset S of V(G), there exist \(\ell \) internally disjoint proper S-trees connecting them. In this paper, we show that for every pair of positive integers k and \(\ell \) with \(k \ge 3\) and \(\ell \le \kappa _k(K_{n,n})\), there exists a positive integer \(N_1=N_1(k,\ell )\) such that \(px_{k,\ell }(K_n) = 2\) for every integer \(n \ge N_1\), and there exists also a positive integer \(N_2=N_2(k,\ell )\) such that \(px_{k,\ell }(K_{m,n}) = 2\) for every integer \(n \ge N_2\) and \(m=O(n^r) (r \ge 1)\). In addition, we show that for every \(p \ge c\root k \of {\frac{\log _a n}{n}}\) (\(c \ge 5\)), \(px_{k,\ell }(G_{n,p})\le 2\) holds almost surely, where \(G_{n,p}\) is the Erd?s–Rényi random graph model.     

A simplified algorithm for the all pairs shortest path problem with O(n 2logn) expected time

The best known expected time for the all pairs shortest path problem on a directed graph with non-negative edge costs is O(n ²logn) by Moffat and Takaoka. Let the solution set be the set of vertices to which the given algorithm has so far established shortest paths. The Moffat-Takaoka algorithm maintains complexities before and after the critical point in balance, which is the moment when the size of the solution set is n?n/logn. In this paper, we remove the concept of critical point, whereby we make the algorithm simpler and seamless, resulting in a simpler analysis.     

An algorithm for optimal difference systems of sets

Difference Systems of Sets (DSS) are combinatorial structures that generalize cyclic difference sets and are used in code synchronization. A DSS is optimal if the associated code has minimum redundancy for the given block length n, alphabet size q, and error-correcting capacity ρ. An algorithm for finding optimal DSS is presented together with tables of optimal solutions found by this algorithm. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Research supported by NSF Grant CCR-0310632.     

A multi-criteria ranking algorithm (MCRA) for determining breast cancer therapy

Breast cancer is the leading cause of cancer deaths among women. The selection of an effective, patient-specific treatment plan for breast cancer has been a challenge for physicians because the decision process involves a vast number of treatment alternatives as well as treatment decision criteria, such as the stage of the cancer (e.g., in situ, invasive, metastasis), tumor characteristics, biomarker-related risks, and patient-related risks. Furthermore, every patient's case is unique, requiring a patient-specific treatment plan, while there is no standard procedure even for a particular stage of the breast cancer. In this paper, we first determine a comprehensive set of criteria for selecting the best breast cancer therapy by interviewing medical oncologists and reviewing the literature. We then present two analytical hierarchy process (AHP) models for quantifying the weights of criteria for breast cancer treatment in two sequential steps: primary and secondary treatment therapy. Using the weights of criteria from the AHP model, we propose a new multi-criteria ranking algorithm (MCRA), which evaluates a large variety of patient scenarios and provides the best patient-tailored breast cancer treatment alternatives based on the input of nine medical oncologists. We then validate the predictions of the multi-criteria ranking algorithm by comparing treatment ranks of the algorithm with ranks of five different oncologists, and show that algorithm rankings match or are statistically significantly correlated with the overall expert ranking in most cases. Our multi-criteria ranking algorithm could be used as an accessible decision-support tool to aid oncologists and educate patients for determining appropriate and effective treatment alternatives for breast cancer. Our approach is also general in the sense that it could be adapted to solve other complex decision-making problems in medicine, healthcare, as well as other service and manufacturing industries.     

An approximation algorithm for a general class of parametric optimization problems

Journal of Combinatorial Optimization - In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is...     

An exponential (matching based) neighborhood for the vehicle routing problem

We introduce an exponential neighborhood for the Vehicle Routing Problem (vrp) with unit customers’ demands, and we show that it can be explored efficiently in polynomial time by reducing its exploration to a particular case of the Restricted Complete Matching (rcm) problem that we prove to be polynomial time solvable using flow techniques. Furthermore, we show that in the general case with non-unit customers’ demands the exploration of the neighborhood becomes an -hard problem.     

An $$O^{*}(1.4366^n)$$-time exact algorithm for maximum $$P_2$$P2-packing in cubic graphs

Given a graph \(G=(V, E)\), a \(P_2\)-packing \(\mathcal {P}\) is a collection of vertex disjoint copies of \(P_2\)s in \(G\) where a \(P_2\) is a simple path with three vertices and two edges. The Maximum \(P_2\)-Packing problem is to find a \(P_2\)-packing \(\mathcal {P}\) in the input graph \(G\) of maximum cardinality. This problem is NP-hard for cubic graphs. In this paper, we give a branch-and-reduce algorithm for the Maximum \(P_2\)-Packing problem in cubic graphs. We analyze the running time of the algorithm using measure-and-conquer and show that it runs in time \(O^{*}(1.4366^n)\) which is faster than previous known exact algorithms where \(n\) is the number of vertices in the input graph.     

An estimation of distribution algorithm for lot-streaming flow shop problems with setup times

Lot-streaming flow shops have important applications in different industries including textile, plastic, chemical, semiconductor and many others. This paper considers an n-job m-machine lot-streaming flow shop scheduling problem with sequence-dependent setup times under both the idling and no-idling production cases. The objective is to minimize the maximum completion time or makespan. To solve this important practical problem, a novel estimation of distribution algorithm (EDA) is proposed with a job permutation based representation. In the proposed EDA, an efficient initialization scheme based on the NEH heuristic is presented to construct an initial population with a certain level of quality and diversity. An estimation of a probabilistic model is constructed to direct the algorithm search towards good solutions by taking into account both job permutation and similar blocks of jobs. A simple but effective local search is added to enhance the intensification capability. A diversity controlling mechanism is applied to maintain the diversity of the population. In addition, a speed-up method is presented to reduce the computational effort needed for the local search technique and the NEH-based heuristics. A comparative evaluation is carried out with the best performing algorithms from the literature. The results show that the proposed EDA is very effective in comparison after comprehensive computational and statistical analyses.     

An integrated simulation model for effective planning of maintenance operations for Saudi Arabian Airlines (SAUDIA)

An effective maintenance system is essential for SAUDIA in order to meet its set objectives. These objectives include minimal flight cancellations, minimal delays, minimal repair turn time, and effective utilization of maintenance resources. In this paper, the elements of an integrated simulation model for SAUDIA have been described. The integrated model consists of several modules. These are planning and scheduling, organization, supply, quality control and performance measures. The required data and software for such a model have been described. Also, the utility of such a model for SAUDIA has been outlined.     

An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence

In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in Parida et al. (2001), Pisanti et al. (2003) and Pelfrêne et al. (2003), its output-polynomial time computability has been still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n in O(n ³) time per motif with O(n) space, in particular O(n ³) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lower bound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach. The results of the computational experiments show that our algorithm can be applicable to huge string data such as genome data in practice, and does not take large additional computational cost compared to usual frequent motif mining algorithms. This work is done during the Hiroki Arimura’s visit in LIRIS, University Claude-Bernard Lyon 1, France.     

Cha n nel assig nme n t problem a nd n-fold t-separa ted $$L(j_1,j_2,\ldo ts,j_m)$$-labeli ng of graphs

This paper considers the channel assignment problem in mobile communications systems. Suppose there are many base stations in an area, each of which demands a number of channels to transmit signals. The channels assigned to the same base station must be separated in some extension, and two channels assigned to two different stations that are within a distance must be separated in some other extension according to the distance between the two stations. The aim is to assign channels to stations so that the interference is controlled within an acceptable level and the spectrum of channels used is minimized. This channel assignment problem can be modeled as the multiple t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labeling of the interference graph. In this paper, we consider the case when all base stations demand the same number of channels. This case is referred as n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labeling of a graph. This paper first investigates the basic properties of n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labelings of graphs. And then it focuses on the special case when \(m=1\). The optimal n-fold t-separated L(j)-labelings of all complete graphs and almost all cycles are constructed. As a consequence, the optimal n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labelings of the triangular lattice and the square lattice are obtained for the case \(j_1=j_2=\cdots =j_m\). This provides an optimal solution to the corresponding channel assignment problems with interference graphs being the triangular lattice and the square lattice, in which each base station demands a set of n channels that are t-separated and channels from two different stations at distance at most m must be \(j_1\)-separated. We also study a variation of n-fold t-separated \(L(j_1,j_2,\ldots ,j_m)\)-labeling, namely, n-fold t-separated consecutive \(L(j_1,j_2,\ldots ,j_m)\)-labeling. And present the optimal n-fold t-separated consecutive L(j)-labelings of all complete graphs and cycles.     

An oracle-based algorithm for robust planning of production routing problems in closed-loop supply chains of beverage glass bottles

The demand for glass bottles is exhibiting an upward trend over time. The manufacturing of glass bottles is costlier in terms of time and resources and is associated with a higher level of heat generation and environmental pollution compared to recycling processes. In response to the aforementioned challenges, companies that use glass bottles need to implement strategies to manage their reverse supply chains in conjunction with their traditional supply chains, as the economic and environmental benefits of returned products are unquestionable. Closed-loop supply chains (CLSCs) integrate forward and reverse flows of products and information. This integration helps companies to have a broader view of the whole chain. Despite these advantages, managing CLSCs can be challenging as they are exposed to many uncertainties regarding supply and demand processes, travel times, and quantity/quality of returned products.In this study, we consider the production planning, inventory management, and vehicle routing decisions of a CLSC of beverage glass bottles. We propose an MILP model and rely on a multi-stage adjustable robust optimization (ARO) formulation to deal with the randomness in both the demand for filled bottles and the requests for pickups of empty bottles. We develop an exact oracle-based algorithm to solve the ARO problem and propose a heuristic search algorithm to reduce the solution time. Our numerical experiments not only show the incompetency of the customary method, namely the affine decision rule approach, but also illustrate how our algorithms can solve the small-size problems and significantly improve the quality of the obtained solution for large problems. Furthermore, our numerical results show that robust plans tend to be sparse, meaning the routes are chosen so that empty bottles are transported to production sites in such a way that fewer new bottles need to be ordered. Thus, robust planning makes the CLSCs more environmentally friendly.     

An Evaluation of the Capacity-building Effects of Participatory GIS (PGIS) for Public Participation in Land Use Planning

Spatial participatory methods called ‘participatory GIS’ (PGIS) are intended to improve public participation for land use planning. An internet PGIS was implemented in Perlis, Malaysia, to examine the public capacity-building effects of PGIS. Two delivery modes (facilitated and self-administered) were evaluated. We found that PGIS significantly enhanced perceived public knowledge about place and land use planning while increasing spatial technology skills, regardless of implementation mode. The results indicate that PGIS can increase public capacity for participating in land use planning, an important finding for developing countries with historically low levels of public participation and low public awareness and knowledge of planning.     

Complementary person-supervisor fit: An investigation of supplies-values (S-V) fit,leader-member exchange (LMX) and work outcomes

By applying the supplies-values (S-V) fit approach from the complementary person-environment (P-E) fit literature to the leader-employee perspective, and drawing upon social exchange theory, we examine how fulfillment of different work values is related to Leader-Member Exchange (LMX) and work outcomes. First, polynomial regression analyses combined with response surface analysis of data collected at two time points (N = 316) showed that LMX (Time 2) was higher the more the leader fulfills the employee's work values (Time 1). Second, LMX (Time 2) was higher when leader supplies (Time 1) and employee work values (Time 1) were both high than when both were low. Third, analyses of data from a sub-sample of matched leader-employee dyads (N = 140), showed that LMX (Time 2) played a mediating role on the relation between S-V fit (Time 1) and work outcomes (Time 2). Specifically, we found eight out of 10 relationships between S-V fit (Time 1) and leader-rated task performance and OCB (Time 2) to be fully mediated by LMX (Time 2). LMX (Time 2) partially mediated the relation between S-V fit (Time 1) and job satisfaction (Time 2) as only two out of five relationships were fully mediated.     

An Integrated Physical Dispersion and Behavioral Response Model for Risk Assessment of Radiological Dispersion Device (RDD) Events

A radiological dispersion device (RDD) or "dirty" bomb is a conventional explosive wrapped in radiological material. Terrorists may use an RDD to disperse radioactive material across a populated area, causing casualties and/or economic damage. Nearly all risk assessment models for RDDs make unrealistic assumptions about public behavior in their health assessments, including assumptions that the public would stand outside in a single location indefinitely. In this article, we describe an approach for assessing the risks of RDD events incorporating both physical dispersion and behavioral response variables. The general approach is tested using the City of Pittsburgh, Pennsylvania as a case study. Atmospheric models simulate an RDD attack and its likely fallout, while radiation exposure models assess fatal cancer risk. We model different geographical distributions of the population based on time of day. We evaluate aggregate health impacts for different public responses (i.e., sheltering-in-place, evacuating). We find that current RDD models in use can be improved with the integration of behavioral components. Using the results from the model, we show how risk varies across several behavioral and physical variables. We show that the best policy to recommend to the public depends on many different variables, such as the amount of trauma at ground zero, the capability of emergency responders to get trauma victims to local hospitals quickly and efficiently, how quickly evacuations can take place in the city, and the amount of shielding available for shelterers. Using a parametric analysis, we develop behaviorally realistic risk assessments, we identify variables that can affect an optimal risk reduction policy, and we find that decision making can be improved by evaluating the tradeoff between trauma and cancer fatalities for various RDD scenarios before they occur.