Fibonacci index and stability number of graphs: a polyhedral study

The Fibonacci index of a graph is the number of its stable sets. This parameter is widely studied and has applications in chemical graph theory. In this paper, we establish tight upper bounds for the Fibonacci index in terms of the stability number and the order of general graphs and connected graphs. Turán graphs frequently appear in extremal graph theory. We show that Turán graphs and a connected variant of them are also extremal for these particular problems. We also make a polyhedral study by establishing all the optimal linear inequalities for the stability number and the Fibonacci index, inside the classes of general and connected graphs of order n.     

On maximum Wiener index of trees and graphs with given radius

Let G be a connected graph of order n. The long-standing open and close problems in distance graph theory are: what is the Wiener index W(G) or average distance \(\mu (G)\) among all graphs of order n with diameter d (radius r)? There are very few number of articles where were worked on the relationship between radius or diameter and Wiener index. In this paper, we give an upper bound on Wiener index of trees and graphs in terms of number of vertices n, radius r, and characterize the extremal graphs. Moreover, from this result we give an upper bound on \(\mu (G)\) in terms of order and independence number of graph G. Also we present another upper bound on Wiener index of graphs in terms of number of vertices n, radius r and maximum degree \(\Delta \), and characterize the extremal graphs.     

Simple and Efficient Graph Compression Schemes for Dense and Complement Graphs

We present two graph compression schemes for solving problems on dense graphs and complement graphs. They compress a graph or its complement graph into two kinds of succinct representations based on adjacency intervals and adjacency integers, respectively. These two schemes complement each other for different ranges of density. Using these schemes, we develop optimal or near optimal algorithms for fundamental graph problems. In contrast to previous graph compression schemes, ours are simple and efficient for practical applications.     

Generalized median graphs and applications

We study the so-called Generalized Median graph problem where the task is to construct a prototype (i.e., a ‘model’) from an input set of graphs. While our primary motivation comes from an important biological imaging application, the problem effectively captures many vision (e.g., object recognition) and learning problems, where graphs are increasingly being adopted as a powerful representation tool. Existing techniques for his problem are evolutionary search based; in this paper, we propose a polynomial time algorithm based on a linear programming formulation. We propose an additional algorithm based on a bi-level method to obtain solutions arbitrarily close to the optimal in (worst case) non-polynomial time. Within this new framework, one can optimize edit distance functions that capture similarity by considering vertex labels as well as he graph structure simultaneously. We first discuss experimental evaluations in context of molecular image analysis problems—he methods will provide the basis for building a topological map of all 23 pairs of the human chromosome. Later, we include (a) applications to other biomedical problems and (b) evaluations on a public pattern recognition graph database. This work was supported by NSF grants CCF-0546509, IIS-0713489, and NIH grant GM 072131-23. The second author was also supported in part by the Department of Biostatistics and Medical Informatics, UW-Madison and UW ICTR, funded through an NIH Clinical and Translational Science Award (CTSA), grant number 1 UL1 RR025011.     

An optimal square coloring of planar graphs

The square coloring of a graph is to color the vertices of a graph at distance at most 2 with different colors. In 1977, Wegner posed a conjecture on square coloring of planar graphs. The conjecture is still open. In this paper, we prove that Wegner’s conjecture is true for planar graphs with girth at least?6.     

A combinatorial theorem on labeling squares with points and its application

In this paper, we present a combinatorial theorem on labeling disjoint axis-parallel squares of edge length two using points. Given an arbitrary set of disjoint axis-parallel squares of edge length two, we show that if we label points on the boundary of all squares (one for each square) and define a distance label graph such that there is an edge between any two labeling points if and only if their L_∞-distance is at most 1 − ε (0 < ε < 1), then the maximum connected component of the graph contains Θ(1/ε) vertices, which is tight. With this theorem we present a new and simple factor-(3 + ε) approximation for labeling points with axis-parallel squares under the slider model. This research is supported by NSF CARGO Grant DMS-0138065.     

CEO-COB prestige distance and change in diversification: Exploring a curvilinear relationship

This study investigates how the prestige distance between a new chief executive officer (CEO) and the chairperson of the board (COB) can influence changes in the firm’s level of diversification. We draw on social comparison theory and activity theory to argue that the prestige distance between a CEO and COB alters the interaction and communication between the two leaders, and accordingly influences the firm’s ability to change its diversification posture. We test our hypotheses on a dataset of 135 firms and find that the prestige distance in CEO-COB dyads has a U-shaped relationship with the change in the firm’s level of diversification. Our results reveal that low CEO-COB prestige distance, and to a lesser extent high CEO-COB prestige distance, creates conditions for greater changes in the firm’s level of diversification. Further, we find that this U-shaped relationship is more pronounced when the CEO-COB dyad has greater age differences and flattens when the dyad shares age similarity.     

基于讨价还价能力的竞争供应链渠道结构绩效研究

本文就独立分销渠道的讨价还价理论在竞争供应链渠道结构面临的问题进行建模,对不同讨价还价能力和产品差异的竞争渠道结构的演化过程进行分析,发现产品与零售商讨价还价能力的差异对竞争渠道结构的选择具有重要影响,并给出了相应结构的演变过程和均衡结果的范围.拓展了Iyery的单渠道结构理论的结果,并为不同环境下渠道结构的选择提供了理论依据.     

A rearrangement of adjacency matrix based approach for solving the crossing minimization problem

In this paper, we first present a binary linear programming formulation for the crossing minimization problem (CMP) in bipartite graphs. Then we use the models of a modified minimum cost flow problem (MMCF) and a travelling salesman problem (TSP) to approximatively solve the CMP by rearranging the adjacency matrix of the bipartite graph. Our approaches are useful for problems defined on dense bipartite graphs. In addition, we compute the exact crossing numbers for some general dense graphs.     

A complexity dichotomy and a new boundary class for the dominating set problem

We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.     

Flows with unit path capacities and related packing and covering problems

Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest. Starting from an LP formulation of the maximum s-t-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting (fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For the fractional problem we present an FPTAS that is based on solving the k shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting O(log?m)-approximation algorithm, where m is the number of arcs in the considered graph. For the multicommodity version of the problem there is an $O(\sqrt{m})Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest. Starting from an LP formulation of the maximum s-t-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting (fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For the fractional problem we present an FPTAS that is based on solving the k shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting O(log m)-approximation algorithm, where m is the number of arcs in the considered graph. For the multicommodity version of the problem there is an O(?m)O(\sqrt{m}) -approximation algorithm. We argue that this performance guarantee is best possible, unless P=NP.     

基于混合加权距离的毕达哥拉斯模糊TOPSIS多属性决策方法研究

针对决策信息为毕达哥拉斯模糊集的多属性决策问题，提出了一种基于混合加权测度的TOPSIS决策方法。在分析了现有距离测度方法不足的基础上，首先给出了一种新的毕达哥拉斯模糊距离测度——毕达哥拉斯模糊有序加权距离（PFOWD），并研究了该测度权重的确定方法；在PFOWD基础上，进一步提出了毕达哥拉斯模糊混合加权距离（PFHWD），同时探讨了其特征和与现有毕达哥拉斯模糊测度的关系；最后提出了一种基于PFHWD测度的毕达哥拉斯模糊TOPSIS多属性方法，并用实例验证了方法的有效性和可行性。     

On risk-averse maximum weighted subgraph problems

In this work, we consider a class of risk-averse maximum weighted subgraph problems (R-MWSP). Namely, assuming that each vertex of the graph is associated with a stochastic weight, such that the joint distribution is known, the goal is to obtain a subgraph of minimum risk satisfying a given hereditary property. We employ a stochastic programming framework that is based on the formalism of modern theory of risk measures in order to find minimum-risk hereditary structures in graphs with stochastic vertex weights. The introduced form of risk function for measuring the risk of subgraphs ensures that optimal solutions of R-MWS problems represent maximal subgraphs. A graph-based branch-and-bound (BnB) algorithm for solving the proposed problems is developed and illustrated on a special case of risk-averse maximum weighted clique problem. Numerical experiments on randomly generated Erdös-Rényi graphs demonstrate the computational performance of the developed BnB.     

Lower bounds for positive semidefinite zero forcing and their applications

The positive semidefinite zero forcing number of a graph is a parameter that is important in the study of minimum rank problems. In this paper, we focus on the algorithmic aspects of computing this parameter. We prove that it is NP-complete to find the positive semidefinite zero forcing number of a given graph, and this problem remains NP-complete even for graphs with maximum vertex degree 7. We present a linear time algorithm for computing the positive semidefinite zero forcing number of generalized series–parallel graphs. We introduce the constrained tree cover number and apply it to improve lower bounds for positive semidefinite zero forcing. We also give formulas for the constrained tree cover number and the tree cover number on graphs with special structures.     

The <Emphasis Type="Italic">p</Emphasis>-maxian problem on block graphs

This paper deals with the p-maxian problem on block graphs with unit edge length. It is shown that the two points with maximum distance provide an optimal solution for the 2-maxian problem of block graphs except for K ₃. It can easily be extended to the p-maxian problem of block graphs. So we solve the p-maxian problem on block graphs in linear time.     

Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees

In this paper we consider the problem of partitioning complete multipartite graphs with edges colored by 2 colors into the minimum number of vertex disjoint monochromatic cycles, paths and trees, respectively. For general graphs we simply address the decision version of these three problems the 2-PGMC, 2-PGMP and 2-PGMT problems, respectively. We show that both 2-PGMC and 2-PGMP problems are NP-complete for complete multipartite graphs and the 2-PGMT problem is NP-complete for bipartite graphs. This also implies that all these three problems are NP-complete for general graphs, which solves a question proposed by the authors in a previous paper. Nevertheless, we show that the 2-PGMT problem can be solved in polynomial time for complete multipartite graphs. Research supported by NSFC.     

Operations Risk Management: Overview of Paul Kleindorfer's Contributions

This paper reviews Paul Kleindorfer's contributions to Operations Management (OM), with a special focus on his research on risk management. An annotated bibliography of selected other contributions reviews the breadth of topics that have occupied Kleindorfer's research attention over his now 45 + years of research. These include optimal control theory, scheduling theory, decision sciences, investment planning and peak load pricing, plus a number of important applications in network industries and insurance. In the area of operations risk management, we review recent work that Kleindorfer and his colleagues in the Wharton Risk Center have undertaken on environmental management and operations, focusing on process safety and environmental risks in the chemical industry. This work is directly related to Kleindorfer's work in the broader area of “sustainable operations”, which he, Kal Singhal and Luk Van Wassenhove recently surveyed as part of the new initiative at POMS to encompass sustainable management practices within the POMS community. Continuing in the area of supply chain risks, the paper reviews Kleindorfer's contributions to the development of an integrated framework for contracting and risk hedging for supply management. The emphasis on alignment of pricing, performance and risk management in this framework is presaged in the work undertaken by Kleindorfer and his co‐authors in the 1980s on after‐sales support services for high‐technology products. This work on supply chain risk, and its successors, is reviewed here in light of its growing importance in managing the unbundled and global supply chains characteristic of the new economy.     

Subset sum problems with digraph constraints

We introduce and study optimization problems which are related to the well-known Subset Sum problem. In each new problem, a node-weighted digraph is given and one has to select a subset of vertices whose total weight does not exceed a given budget. Some additional constraints called digraph constraints and maximality need to be satisfied. The digraph constraint imposes that a node must belong to the solution if at least one of its predecessors is in the solution. An alternative of this constraint says that a node must belong to the solution if all its predecessors are in the solution. The maximality constraint ensures that no superset of a feasible solution is also feasible. The combination of these constraints provides four problems. We study their complexity and present some approximation results according to the type of input digraph, such as directed acyclic graphs and oriented trees.     

Implementation of new technology: towards greater manufacturing flexibility

Changes in market characteristics over the past several years are forcing firms to eliminate&sol;minimize dependency on costly buffers of capacity, lead time, or inventory. One way to accomplish this is via appropriate adaptation and enhancement of existing technological infrastructure. Recent technological advances present firms with a wide array of alternative technologies. In this paper, we discuss the impact of new technology on the manufacturing environment and the problems associated with its implementation. We present an integrated framework for implementing such technology based on a consistent hierarchy of organizational objectives and a general foundation of constraint theory.     

On the cores of games arising from integer edge covering functions of graphs

In this paper, we study cooperative games arising from integer edge covering problems on graphs. We introduce two games, a rigid k-edge covering game and its relaxed game, as generalizations of a rigid edge covering game and its relaxed game studied by Liu and Fang (2007). Then we give a characterization of the cores of both games, find relationships between them, and give necessary and sufficient conditions for the balancedness of a rigid k-edge covering game and its relaxed game.