A tromino tiling problem is a packing puzzle where we are given a region of connected lattice squares and we want to decide whether there exists a tiling of the region using trominoes with the shape of an L. In this work we study a slight variation of the tromino tiling problem where some positions of the region have pegs and each tromino comes with a hole that can only be placed on top of the pegs. We present a characterization of this tiling problem with pegs using flow networks and show that (i) there exists a linear-time parsimonious reduction to the maximum-flow problem, and (ii) counting the number of such tilings can be done in linear-time. The proofs of both results contain algorithms that can then be used to decide the tiling of a region with pegs in O(n) time.

In classical network reliability, the system under study is a network with perfect nodes and imperfect links that fail randomly and independently. The probability that a given subset of terminal nodes belongs to the same connected component is called classical or ‐Terminal reliability. Although (and because) the classical reliability computation belongs to the class of ‐Hard problems, the literature offers many methods for this purpose, given the importance of the models. This article deals with diameter‐constrained reliability, where terminal nodes are further required to be connected by hops or fewer ( is a given strictly positive parameter of the metric called its diameter). This metric was defined in 2001, inspired by delay‐sensitive applications in telecommunications. Factorization theory is fundamental for the classical network reliability evaluation, and today it is a mature area. However, its extension to the diameter‐constrained context requires at least the recognition of irrelevant links, which is an open problem. In this article, irrelevant links are efficiently determined in the most used case, where , thus providing a first step toward a Factorization theory in diameter‐constrained reliability. We also analyze the metric in series‐parallel and composition graphs. The article closes with a Factoring algorithm and a discussion of trends for future work. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(4), 283–291 2017

Let be a simple graph with vertices and edges, a subset of terminals, a vector and a positive integer , called the diameter. We assume vertices are perfect but edges fail stochastically and independently, with probabilities . The diameter constrained reliability (DCR) is the probability that the terminals of the resulting subgraph remain connected by paths composed of or fewer edges. This number is denoted by . The general DCR computation problem belongs to the class of ‐hard problems. The contributions of this article are threefold. First, the computational complexity of DCR‐subproblems is discussed in terms of the number of terminal vertices and the diameter . Either when or when and is fixed, the DCR problem belongs to the class of polynomial‐time solvable problems. The DCR problem becomes ‐hard when is a fixed input parameter and . The cases where or is a free input parameter and is fixed have not been studied in the prior literature. Here, the ‐hardness of both cases is established. Second, we categorize certain classes of graphs that allow the DCR computation to be performed in polynomial time. We include graphs with bounded corank, graphs with bounded genus, planar graphs, and in particular, Monma graphs, which are relevant in robust network design. Third, we introduce the problem of analyzing the asymptotic properties of the DCR measure in networks that grow infinitely following given probabilistic rules. We introduce basic results for Gilbert's random graph model. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(4), 296–305 2015

Abstract Lower and upper bounds on the order of digraphs and generalized p‐cycles with a specified maximum degree and unilateral diameter are given for generic values of the parameters. Infinite families of digraphs attaining the bounds asymptotically or even exactly are presented. In particular, optimal results are proved for bipartite digraphs (p = 2) and digraphs with unilateral diameter 3. © 2003 Wiley Periodicals, Inc.

Large digraphs of a specified maximum degree and unilateral diameter are given for small values of these parameters. The constructions are based on different techniques such as voltage digraphs, digraph products, join of cycles, and vertex duplication. Finally, a table with the results is given. © 2000 John Wiley & Sons, Inc.