Factorizations of complete graphs into caterpillars of diameter 5

We examine factorizations of complete graphs K_2n into caterpillars of diameter 5. First we present a construction generalizing some previously known methods. Then we use the new method along with some previous partial results to give a complete characterization of caterpillars of diameter 5, which factorize the complete graph K_2n.     

The threshold for combs in random graphs

For let denote the tree consisting of an ‐vertex path with disjoint ‐vertex paths beginning at each of its vertices. An old conjecture says that for any the threshold for the random graph to contain is at . Here we verify this for with any fixed . In a companion paper, using very different methods, we treat the complementary range, proving the conjecture for (with ). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 794–802, 2016     

The number of spanning trees in an (r,s)‐semiregular graph and its line graph

For a graph G, a “spanning tree” in G is a tree that has the same vertex set as G. The number of spanning trees in a graph (network) G, denoted by t(G), is an important invariant of the graph (network) with lots of decisive applications in many disciplines. In the article by Sato (Discrete Math. 2007, 307, 237), the number of spanning trees in an (r, s)‐semiregular graph and its line graph are obtained. In this article, we give short proofs for the formulas without using zeta functions. Furthermore, by applying the formula that enumerates the number of spanning trees in the line graph of an (r, s)‐semiregular graph, we give a new proof of Cayley's Theorem. © 2013 Wiley Periodicals, Inc.     

Degradative encryption: An efficient way to protect SPIHT compressed images

Degradative encryption, a new selective image encryption paradigm, is proposed to encrypt only a small part of image data to make the detail blurred but keep the skeleton discernible. The efficiency is further optimized by combining compression and encryption. A format-compliant degradative encryption algorithm based on set partitioning in hierarchical trees (SPIHT) is then proposed, and the scheme is designed to work in progressive mode for gaining a tradeoff between efficiency and security. Extensive experiments are conducted to evaluate the strength and efficiency of the scheme, and it is found that less than 10% data need to be encrypted for a secure degradation. In security analysis, the scheme is verified to be immune to cryptographic attacks as well as those adversaries utilizing image processing techniques. The scheme can find its wide applications in online try-and-buy service on mobile devices, searchable multimedia encryption in cloud computing, etc.     

The Tree of Hubs Location Problem

This paper presents the Tree of Hubs Location Problem. It is a network hub location problem with single assignment where a fixed number of hubs have to be located, with the particularity that it is required that the hubs are connected by means of a tree. The problem combines several aspects of location, network design and routing problems. Potential applications appear in telecommunications and transportation systems, when set-up costs for links between hubs are so high that full interconnection between hub nodes is prohibitive. We propose an integer programming formulation for the problem. Furthermore, we present some families of valid inequalities that reinforce the formulation and we give an exact separation procedure for them. Finally, we present computational results using the well-known AP and CAB data sets.     

Models for concurrent product and process design

We propose procedures to address product design and manufacturing process configurations concurrently in environments characterized by large degrees of product proliferation. Exploiting the intrinsic flexibility of product and process design, we present two approaches that synchronize production flows through the manufacturing system. These approaches integrate product and manufacturing system design decisions with operational concerns and provide powerful means for managing production in environments characterized by a proliferation of products. Experimental results show that the proposed methods can substantially reduce manufacturing lead times, work in process (WIP), and overall system complexity.     

No-arbitrage conditions,scenario trees,and multi-asset financial optimization

Many numerical optimization methods use scenario trees as a discrete approximation for the true (multi-dimensional) probability distributions of the problem’s random variables. Realistic specifications in financial optimization models can lead to tree sizes that quickly become computationally intractable. In this paper we focus on the two main approaches proposed in the literature to deal with this problem: scenario reduction and state aggregation. We first state necessary conditions for the node structure of a tree to rule out arbitrage. However, currently available scenario reduction algorithms do not take these conditions explicitly into account. State aggregation excludes arbitrage opportunities by relying on the risk-neutral measure. This is, however, only appropriate for pricing purposes but not for optimization. Both limitations are illustrated by numerical examples. We conclude that neither of these methods is suitable to solve financial optimization models in asset–liability or portfolio management.     

Flexible isosurfaces: Simplifying and displaying scalar topology using the contour tree

The contour tree is an abstraction of a scalar field that encodes the nesting relationships of isosurfaces. We show how to use the contour tree to represent individual contours of a scalar field, how to simplify both the contour tree and the topology of the scalar field, how to compute and store geometric properties for all possible contours in the contour tree, and how to use the simplified contour tree as an interface for exploratory visualization.