Search

We study the parameterized complexity of domination problems on sparse graphs and beyond. The nowhere dense classes of graphs have been proposed as the main model for sparseness that can be utilized algorithmically. The class of d-degenerate graphs is not nowhere dense, yet domination remains fixed-parameter tractable. Both nowhere dense classes of graphs and d-degenerate graph classes are biclique-free classes, meaning there is an integer t such that no graph in the class contains K t , t as a subgraph. In this paper we show that various domination problems are fixed-parameter tractable on biclique-free classes of graphs. Our algorithms are simple and rely on results from extremal graph theory that bound the number of edges in a t-biclique free graph. In particular, the problems k -Dominating Set , Connected k -Dominating Set , Independent k -Dominating Set and Minimum Weight k -Dominating Set are shown to be FPT, when parameterized by t + k , on graphs not containing K t , t as a subgraph. With the exception of Connected k -Dominating Set all described algorithms are linear in the size of the input graph.

Given a vertex-weighted graph G = ( V , E ) and a positive integer k ≥ 2, the minimum weight vertex cover Pk (MWVCPk) problem is to find a vertex subset F ⊆ V with minimum total weight such that every path of order k in G contains at least one vertex in F. For any integer k ≥ 2, the MWVCPk problem for general graphs is NP-hard. In this paper, we restrict our attention to the MWVCP3 problem and present a multi-start iterated greedy algorithm to solve the MWVCP3 problem. The experiments are carried out on randomly generated instances with up to 1000 vertices and 250000 edges. Our work is the first one to adopt heuristic algorithms to solve the MWVCP3 problem, and the experimental results show that our algorithm performs reasonably well in practice.

Single-commodity network design considers an edge-weighted, undirected graph with a supply/demand value at each node. It asks for minimum weight capacities such that each node can exactly send (or receive) its supply (or demand). In the robust variant, the supply or demand values may assume any realization in a given uncertainty set. One popular set is the well-known Hose polytope, which specifies an interval for the supply/demand at each node, while ensuring that the total supply and demand are balanced across the whole network. While previous work has established the Hose uncertainty set as a tractable choice, it can yield unnecessarily expensive solutions because it admits many unlikely supply and demand scenarios. In this paper, we propose a generalization of the Hose polytope that more realistically captures existing interdependencies among nodes in real life networks, and we show how to extend the state-of-the-art cutting plane algorithm for solving the single-commodity robust network design problem in view of this new uncertainty set. Our computational studies across multiple robust network design instances illustrate that the new set can provide significant cost savings without sacrificing numerical tractability.

A perfect Roman dominating function on a graph $$G =(V,E)$$ is a function $$f: V \longrightarrow \{0, 1, 2\}$$ satisfying the condition that every vertex u with $$f(u) = 0$$ is adjacent to exactly one vertex v for which $$f(v)=2$$ . The weight of a perfect Roman dominating function f is the sum of the weights of the vertices. The perfect Roman domination number of G, denoted by $$\gamma _{R}^{p}(G)$$ , is the minimum weight of a perfect Roman dominating function in G. In this paper, we first show that the decision problem associated with $$\gamma _{R}^{p}(G)$$ is NP-complete for bipartite graphs. Then, we prove that for every tree T of order $$n\ge 3$$ , with $$\ell $$ leaves and s support vertices, $$\gamma _R^P(T)\le (4n-l+2s-2)/5$$ , improving a previous bound given in Henning et al. (Discrete Appl Math 236:235–245, 2018).

Let k ≥ 1 be an integer and G be a simple and finite graph with vertex set V(G). A signed double Roman k-dominating function (SDRkDF) on a graph G is a function f:V(G) → {−1,1,2,3} such that (i) every vertex v with f(v) = −1 is adjacent to at least two vertices assigned a 2 or to at least one vertex w with f(w) = 3, (ii) every vertex v with f(v) = 1 is adjacent to at least one vertex w with f(w) ≥ 2 and (iii) ∑u∈N[v]f(u) ≥ k holds for any vertex v. The weight of a SDRkDF f is ∑u∈V(G) f(u), and the minimum weight of a SDRkDF is the signed double Roman k-domination number γksdR(G) of G. In this paper, we investigate the signed double Roman k-domination number of trees. In particular, we present lower and upper bounds on γksdR(T) for 2 ≤ k ≤ 6 and classify all extremal trees.

A k-path vertex cover (VCPk) is a vertex set C of graph G such that every path of G on k vertices has at least one vertex in C. Because of its background in keeping data integrality of a network, minimum VCPk problem (MinVCPk) has attracted a lot of researches in recent years. This paper studies the minimum weight connected VCPk problem (MinWCVCPk), in which every vertex has a weight and the VCPk found by the algorithm induces a connected subgraph and has the minimum weight. It is known that MinWCVCPk is set-cover-hard. We present two polynomial-time approximation algorithms for MinWCVCP3. The first one is a greedy algorithm achieving approximation ratio 3ln n. The difficulty lies in its analysis dealing with a non-submodular potential function. The second algorithm is a 2-stage one, finding a VCP3 in the first stage and then adding more vertices for connection. We show that its approximation ratio is at most ln δ max + 4 + ln 2 , where δmax is the maximum degree of the graph. Considering the inapproximability of this problem, this ratio is asymptotically tight.

Sandwich core materials that offer superior mechanical properties at minimum weight are essential in designing high-performance sandwich structures. Hierarchical materials are ideal templates for this purpose. In this paper, we investigate the mechanical performance of a pyramidal–pyramidal hierarchical lattice material to highlight its potential as the core material for sandwich structures. Three-dimensional failure mechanism maps for the pyramidal–pyramidal hierarchical lattice material are developed under different loading conditions and the results are compared to finite element simulations. Next, we study the mechanical response and failure modes of a sandwich panel with self-similar pyramidal lattice core construction subjected to in-plane compression and three-point bending. The current study indicates that the pyramidal–pyramidal hierarchical configuration can improve the load bearing capacity and core buckling resistance of the sandwich structures at low density. The study provides insights into the role of structural hierarchy in tuning the mechanical response of the lattice materials and expands the application envelope of lightweight sandwich structures by effectively increasing the structural buckling resistance.

In this paper, we discuss the design and analysis of polynomial time algorithms for two problems associated with a linearly infeasible system of Unit Two Variable Per Inequality (UTVPI) constraints, viz., (a) the read-once refutation (ROR) problem, and (b) the literal-once refutation (LOR) problem. Recall that a UTVPI constraint is a linear relationship of the form: $$a_{i}\cdot x_{i}+a_{j} \cdot x_{j} \le b_{ij}$$ , where $$a_{i},a_{j} \in \{0,1,-1\}$$ . A conjunction of such constraints is called a UTVPI constraint system (UCS) and can be represented in matrix form as: $$\mathbf{A \cdot x \le b}$$ . These constraints find applications in a host of domains including but not limited to operations research and program verification. For the linear system $$\mathbf{A\cdot x \le b}$$ , a refutation is a collection of m variables $$\mathbf{y}=[y_{1},y_{2},\ldots , y_{m}]^{T} \in \mathfrak {R}^{m}_{+}$$ , such that $$\mathbf{y\cdot A =0}$$ , $$\mathbf{y \cdot b } < 0$$ . Such a refutation is guaranteed to exist for any infeasible linear program, as per Farkas’ lemma. The refutation is said to be read-once, if each $$y_{i} \in \{0,1\}$$ . Read-once refutations are incomplete in that their existence is not guaranteed for infeasible linear programs, in general. Indeed they are not complete, even for UCSs. Hence, the question of whether an arbitrary UCS has an ROR is both interesting and non-trivial. In this paper, we reduce this problem to the problem of computing a minimum weight perfect matching (MWPM) in an undirected graph. This transformation results in an algorithm that runs in in time polynomial in the size of the input UCS. Additionally, we design a polynomial time algorithm (also via a reduction to the MWPM problem) for a variant of read-once resolution called literal-once resolution. The advantage of reducing our problems to the MWPM problem is that we can leverage recent advances in algorithm design for the MWPM problem towards solving the ROR and LOR problems in UCSs. Finally, we show that another variant of read-once refutation problem called the non-literal read-once refutation (NLROR) problem is NP-complete in UCSs.

Weight reduction of Unmanned Aerial Vehicle (UAV) components and systems is one of the most essential factors for aviation. Take-off gross weight can be divided into crew weight, payload, fuel, and empty weight. The empty weight is divided into the structure, engine/s, landing gear, avionics and fixed equipment. Engine/s, landing gear, avionics and fixed equipment are selective items. Weight optimization can be made for structure and landing gear to minimize aircraft total weight. The main objective of the present study is to optimize weight and reach safe landing for a medium range UAV landing gear. The reduced weight can be used to increase payload and/or fuel to increase range or endurance of the UAV. In the present study, ANSYS shape (Topology) optimization tool is used to get a proposed shape for the UAV landing gear. Then parametric size optimization of the shape proposed was done. Design of experiment (DOE) technique is used in order to get the minimum weight for the landing gear at a specified stress limit. Aluminum alloy 7075-T61 and bi-directional carbon fiber which are the most common used materials in UAVs landing gear were used, It was found that using topology weight optimization technique reduces Aluminum Alloy landing gear weight by (30.4 %) changing the material to be bi-directional carbon fiber without optimization reduce landing gear weight with additional value (27.9 %). Optimizing bi-directional carbon fiber landing gear reduces the weight with additional value (4 %) to be the total weight ratio by (62.3 %). The optimization technique for weight optimization is a guide to optimize any other type of landing / part to minimize the total weight for the Unmanned Aerial Vehicle.

A fundamental quest in the theory of computing is to understand the power of randomness. It is not known whether every problem with an efficient randomized algorithm also has one that does not use randomness. One of the extensively studied problems under this theme is that of perfect matching. The perfect matching problem has a randomized parallel (NC) algorithm based on the Isolation Lemma of Mulmuley, Vazirani, and Vazirani. It is a long-standing open question whether this algorithm can be derandomized. In this article, we give an almost complete derandomization of the Isolation Lemma for perfect matchings in bipartite graphs. This gives us a deterministic parallel (quasi-NC) algorithm for the bipartite perfect matching problem. Derandomization of the Isolation Lemma means that we deterministically construct a weight assignment so that the minimum weight perfect matching is unique. We present three different ways of doing this construction with a common main idea.

A classification of extremal double circulant self-dual codes of lengths up to 88 is known. We extend this classification to length 96. We give a classification of extremal double circulant self-dual codes of lengths 90, 92, 94 and 96. We also classify double circulant self-dual codes with parameters [90, 45, 14] and [96, 48, 16]. In addition, we demonstrate that no double circulant self-dual [90, 45, 14] code has an extremal self-dual neighbor, and no double circulant self-dual [96, 48, 16] code has a self-dual neighbor with minimum weight at least 18.

The Inverse-PageRank-PSO (I-PR-PSO) algorithm, an optimizer based both on the Particle Swarm Optimization (PSO) algorithm and the PageRank algorithm - used by the well known search engine Google - is applied to continuum structural topology optimization. To deal with the classical continuum mechanics problems of the literature, such as checkerboards in the resulted topologies, the algorithm is interfaced with the Evolutionary Structural Optimization (ESO) algorithm. Several well-studied examples from structural topology optimization problems of minimum weight and minimum compliance are used to demonstrate the efficiency of the newly developed algorithm. The results show the possibility to treat two-objectives problems, even if the two objectives are apparently conflicting, finally finding a compromize that minimizes both the volume and the compliance of the structure.

In a finite undirected graph G, a vertex v dominates itself and its neighbors. A vertex set D is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in G, is well known to be NP -complete for graphs of maximum degree 3. We say that an e.d.s. D of G is k-bounded (k-b.e.d.s. for short) if the degree of every vertex in D is at most k in G. The task of the k-Bounded Weighted Efficient Domination (k-BWED) problem is to determine whether a given vertex-weighted graph G admits a k-b.e.d.s., and if so, to compute one of minimum weight. It easily follows from the NP -completeness of ED for graphs of maximum degree 3 that the k-BWED problem is NP -complete for every k ≥ 3 , and clearly, the k-BWED problem is solvable in linear time for k ≤ 1 . In this note, we show that the 2-BWED problem is solvable in time O ( | V ( G ) | ( | V ( G ) | + | E ( G ) | ) ) , thus obtaining a dichotomy of the complexity status of k-BWED over all k ≥ 0 .

In this paper, we study families of optimal frames of aircraft, as the fuselage cross-section vary, in the preliminary design. A complete closed-form solution of displacements and stresses for a circular arc, already introduced in a previous paper of the authors, is applied to study, in a wide generality, a fuselage cross-section made of tangent circular arcs, connected together in a $${\mathscr {C}}^1$$ -class curve. The closed-form solution is used here for two optimization case studies involving such piece-wise tangent cross-sections. First, we obtain minimum weight configurations of frames under pressurization, and also the effect of a small eccentricity with respect to the perfect circular fuselage is investigated; then, the constraints due to the presence of two floor decks are introduced. Second, the analytic solutions are validated by means of a finite element simulation in Abaqus and, to show the generality of the closed-form solution, the case studies are dedicated to non-conventional aircraft. Finally, we investigate the effects of the ellipticity ratio and the presence of a vertical and horizontal truss by means of finite element beam models.

The minimum weight vertex cover (MWVC) problem is a well known NP-hard problem with various real-world applications . In this paper, we design an efficient algorithm named FastWVC to solve MWVC problem in massive graphs. To this end, we propose a construction procedure, which aims to generate a quality initial vertex cover in short time. We also propose a new exchange step for reconstructing a vertex cover. Additionally, a cost-effective strategy is used for choosing adding vertices, which can accelerate the algorithm. Experiments on 102 instances were conducted to confirm the effectiveness of our algorithm. The results show that the FastWVC algorithm outperforms other algorithms in terms of both solution quality and computational time in most of the instances. We also carry out experiments that analyze the effectiveness of the underlying ideas.

An Italian dominating function (IDF) on a graph $G=(V,E)$ is a function $f:V\rightarrow \{0,1,2\}$ satisfying the condition that for every vertex $v\in V$ with $f(v)=0$ , either $v$ is adjacent to a vertex assigned 2 under $f$ , or $v$ is adjacent to at least two vertices assigned 1 under $f$ . The weight of an IDF $f$ is the value $\sum _{v\in V}f(v)$ . The Italian domination number of a graph $G$ is the minimum weight of an IDF on $G$ . The Italian reinforcement number of a graph is the minimum number of edges that have to be added to the graph in order to decrease the Italian domination number. In this paper, we initiate the study of Italian reinforcement number and we present some sharp upper bounds for this parameter. In particular, we determine the exact Italian reinforcement numbers of some classes of graphs.

In this paper we continue the study of signed double Roman dominating functions in graphs. A signed double Roman dominating function (SDRDF) on a graph G = (V,E) is a function f : V(G)  {-1,1,2,3} having the property that for each v  V(G), f [v] ≥ 1, and if f (v)= -1, then vertex v has at least two neighbors assigned 2 under f or one neighbor w with f(w)=3, and if f(v)=1, then vertex v must have at leat one neighbor w with f (w)≥2. The weight of a SDRDF is the sum of its function values over all vertices. The signed double Roman domination number γsdR(G) is the minimum weight of a SDRDF on G. We present several lower bounds on the signed double Roman domination number of a graph in terms of various graph invariants. In particular, we show that if G is a graph of order n and size m with no isolated vertex, then γsdR(G) ≥ 19n-24m/9 and γsdR(G)≥4 √n/3-n. Moreover, we characterize the graphs attaining equality in these two bounds.

Domination number is of practical interest in several theoretical and applied scenes. In the problem of wireless networking, the dominating idea is used to deduce an efficient route within the adhoc mobilenetworks. It has also been used for the summarization of documents and making a design of secure web-systems for electrical recursive grids. In this paper, we explore an important class of domination numbers, which is the 2-rainbow independent dominating function (2RiDF) on graphs. The minimum weight of a 2RiDF on a graph G is called the 2-rainbow independent domination number of G. A graph G is 2-rainbow independent domination stable if the 2-rainbow independent domination number of G remains unchanged under removal of any vertex. As a result, we characterize 2-rainbow independent domination stable tree-networks and study the effect of edge removal on 2-rainbow independent domination number in trees.

In this paper, we consider additive circulant graph codes which are self-dual additive \begin{document}$ \mathbb{F}_4 $\end{document} -codes. We classify all additive circulant graph codes of length \begin{document}$ n = 30, 31 $\end{document} and \begin{document}$ 34 \le n \le 40 $\end{document} having the largest minimum weight. We also classify bordered circulant graph codes of lengths up to 40 having the largest minimum weight.

This paper presents a multi-level aeroelastic tailoring framework for the optimisation of composite aircraft wings. The framework is capable of structural sizing and produces detailed composite ply configurations through robust and reliability-based design optimisation, and is demonstrated on a representative regional jet airliner finite element wing box model. The optimisation procedure is divided into two levels. The first level optimises the wing structure for minimum weight subject to multiple constraints including strain, buckling, aeroelastic stability and gust response. These first level solutions are then fed into the second level to be further optimised for robustness or reliability by considering uncertainties in material properties at ply level. Both the principles of robust and reliability-based design optimisation can also be used in combination to ensure a balance between the robustness and reliability of the structural performance. In order to keep computations to an acceptable cost, the second level optimisation employs the Polynomial Chaos Expansion method to approximate the effect of probabilistic uncertainty on structural performance. In comparison to the original benchmark wing, the framework produces an overall weight reduction of 32.1%, despite a 1.5% increase from the first to the second level optimisation that accounts for stochastic design variations.

Given the extensive utilization of cantilever retaining walls in construction and development projects, their optimal design and analysis with proper attention to seismic loads is a typical engineering problem. This research presents a new algorithm for pseudo-static analysis of retaining walls employing upper bound method. The algorithm can be utilized to design and check the external and internal stability of the wall based on the proposed mechanism. One of the main features of this algorithm is its ability to determine the critical condition of failure wedges, the minimum safety factor and maximum force acting on the wall, as well as the minimum weight of the wall, simultaneously, by effectively using the multi-objective optimization. The results obtained by the proposed failure mechanisms show that, while using the upper bound limit analysis approach, the active force should be maximized concurrent with optimizing the direction of the plane passing through the back of the heel. The present study also applies the proposed algorithm to determine the critical direction of the earthquake acceleration coefficient. The critical direction of earthquake acceleration coefficient is defined as the direction that maximizes the active force exerted on the wall and minimizes the safety factor for wall stability. The results obtained in this study are in good agreement with those of similar studies carried out based on the limit equilibrium method and finite element analysis. The critical failure mechanisms were determined via optimization with genetic algorithm.

The ply-drop (PD) is termination of specific plies at rib-axis for getting tapered laminates. The present optimization study aims to achieve minimum weight tapered wing panels laminates by PD followed by ply-migrations (PM). The PM are required for ply-continuity (blending) and achieving smooth external aerodynamic surface . A genetic-algorithm mutation operator and fitness based search algorithm is developed in the present study for the optimization. The laminate weight minimization has been achieved as goal of multi-objective optimization (MOO), by utilizing excess design margins of Tsai-Wu first ply failure-index (FI) and wing tip lateral deflection . The finite-element (FE) model of laminate is a set of discrete laminates (chromosomes) between ribs with continuity by virtue of ply-orientations . To select best fit laminate, ply orientations were randomly selected and perturbed for thickness during optimization. The fitness function for evaluating chromosomes is a composite function of multi-objective design requirements and design constraints. The algorithm submits orientation/thickness combinations to ABAQUS/CAE by python-script for function evaluation. The application of algorithm over an initially assumed quasi-isotropic laminate of uniform thickness showed 57% weight reduction for a fighter aircraft’s wing panel. The optimization process is automated making PD practically viable in the design process itself.

Designing sophisticate ship structures that satisfy several design criteria simultaneously with minimum weight and cost is an important engineering issue. For a ship structure composed of a shell and stiffeners, this issue is more serious because their mutual effect has to be addressed. In this study, a two-stage optimization method is proposed for the conceptual design of stiffeners in a ship's prow. In the first stage, a topology optimization method is used to determine a potential stiffener distribution based on the optimal results, whereupon stiffeners are constructed according to stiffener generative theory and the material distribution. In the second stage, size optimization is conducted to optimize the plate and stiffener sections simultaneously based on a parametric model. A final analysis model of the ship-prow structure is presented to assess the validity of this method. The analysis results show that the two-stage optimization method is effective for stiffener conceptual design, which provides a reference for designing actual stiffeners for ship hulls. Keywords: Prow stiffener, Two-stage optimization, Manufacturing constraints, Multi-objective function, Compromise programming

An outer-independent Italian dominating function (OIIDF) on a graph G with vertex set V(G) is defined as a function f : V(G) → {0, 1, 2}, such that every vertex v ∈ V(G) with f(v) = 0 has at least two neighbors assigned 1 under f or one neighbor w with f(w) = 2, and the set {u ∈ V | f (u) = 0} is independent. The weight of an OIIDF f is the value w(f) = Σu∈V(G) f(u). The minimum weight of an OIIDF on a graph G is called the outer-independent Italian domination number γoiI(G) of G. In this paper, we initiate the study of the outer-independent Italian domination number and present the bounds on the outer-independent Italian domination number in terms of the order, diameter, and vertex cover number. In addition, we establish the lower and upper bounds on γoiI (T) when T is a tree and characterize all extremal trees constructively. We also give the Nordhaus-Gaddum-type inequalities.

A graph is k-connected if it has k pairwise internally node disjoint paths between every pair of its nodes. A subset S of nodes in a graph G is a k-connected set if the subgraph G [ S ] induced by S is k-connected; S is an m-dominating set if every v ∈ V ∖ S has at least m neighbors in S. If S is both k-connected and m-dominating then S is a k-connected m-dominating set, or ( k , m ) -cds for short. In the k -Connected m -Dominating Set ( ( k , m ) -CDS ) problem the goal is to find a minimum weight ( k , m ) -cds in a node-weighted graph. We consider the case m ≥ k and obtain the following approximation ratios. For unit disc graphs we obtain ratio O ( k ln ⁡ k ) , improving the ratio O ( k 2 ln ⁡ k ) of [1] , [2] . For general graphs we obtain the first non-trivial approximation ratio O ( k 2 ln ⁡ n ) .

A set D of vertices in a graph G is an efficient dominating set (e.d.s. for short) of G if D is an independent set and every vertex not in D is adjacent to exactly one vertex in D. The efficient domination (ED) problem asks for the existence of an e.d.s. in G. The minimum weighted efficient domination problem (MIN-WED for short) is the problem of finding an e.d.s. of minimum weight in a given vertex-weighted graph. Brandstadt, Ficur, Leitert and Milanic (2015) [3] stated the running times of the fastest known polynomial-time algorithms for the MIN-WED problem on some graphs classes by using a Hasse diagram. In this paper, we update this Hasse diagram by showing that, while for every integer d such that d = 3 k or d = 3 k + 2 , where k ≥ 1 , the ED problem remains NP-complete for graphs of diameter d, the weighted version of the problem is solvable in time O ( | V ( G ) | + | E ( G ) | ) in the class of diameter three bipartite graphs and in time O ( | V ( G ) | 5 ) in the class of diameter three planar graphs.

Generally, heavier noise control treatments are favored over lighter treatments since heavier acoustical materials generally insulate (block) noise sources more effectively than do lighter materials. In automotive applications, however, heavier materials cannot always be adopted because of concerns about the total weight of the vehicle. Thus, it would be useful to identify lightweight acoustical treatments that can mitigate vehicle interior noise. Automotive sound packages have both absorption and transmission characteristics, and there is inevitably a trade-off between these two. Therefore, it is important to study the exchange between the absorption and transmission of acoustical materials particularly as it pertains to weight. Here, we describe a procedure, based on plane wave analysis, that can be used to identify weight reduction opportunities by adjusting the acoustical properties of a generic sound package, consisting of a fibrous layer and a flexible microperforated panel surface treatment, so that it meets a target sound pressure level in a downstream interior space. It has been found for the configuration studied here that there are lightweight sound package configurations that can maintain acoustical performance equivalent to that of heavier noise treatments, and further, it has been found that the lightest treatments tend to favor barrier performance rather than absorption. Further, the impact of acoustical leaks is considered, and it has been found that even very small leaks can result in a very substantial weight penalty if a specified level of acoustical performance is to be ensured.

Ultralight all-metallic sandwich cylindrical shells with corrugated cores are designed and fabricated using a method involving tamping and shape correction. Quasi-static axial compressive behaviors of the sandwich shells are investigated using a combined experimental, theoretical and numerical approach. Based on the analytical model and numerical approach, systematic parametric study is carried out to explore the effects of key geometrical parameters on the failure load and energy absorption capacity. Minimum weight design as a function of the failure load is subsequently carried out for the proposed sandwich shell. As an attempt for further performance enhancement, the foam-filled corrugated-core sandwich cylindrical shell is proposed and a preliminary experimental study is carried out. The superiority of sandwich shells over monolithic shells in terms of initial failure load and energy absorption is clearly demonstrated, potentially important for applications demanding simultaneous ultra-lightweight, load-bearing and energy absorption. Keywords: Sandwich cylindrical shell, Corrugated core, Axial compression, Minimum weight design

Computing the weighted girth, which is the sum of weights of edges in the minimum weight cycle, is an important problem in network analysis. The problem for distributively computing girth in unweighted graphs has garnered lots of attention, but there are few studies in weighted graphs. In this paper, we propose a distributed randomized algorithm for computing the weighted girth in weighted graphs with integral edge weights in the range [1, nc], where n is the number of vertices and c is a constant. The algorithm is devised under the standard synchronous $${\cal C}{\cal O}{\cal N}{\cal G}{\cal E}{\cal S}{\cal T}$$ model, which limits each vertex can only transfer O(log n) bits information along each incident edge in a round. The upper bound of the algorithm is O(n log2n) rounds. We also prove the lower bound for computing the weighted girth is Ω(D + n/ log n) where D is the hop diameter of the weighted graph. This means our distributed algorithm is optimal within a factor of O(log3n).

Shortest path finding is the building block of various applications in road networks and the index-based algorithms, especially hub labeling, can boost the query performance dramatically. However, the traffic condition keeps changing in real life, making the pre-computed index unable to answer the query correctly. In this work, we adopt the state-of-the-art tree decomposition-based hub labeling as the underlying index, and design efficient algorithms to incrementally maintain the index. Specifically, we first analyze the structural stability of the index in dynamic road networks which enables us to concentrate on label value maintenance. We then introduce the minimum weight property and minimum distance property to guarantee the index correctness without graph traversal. Moreover, we propose the star-centric paradigm for tracing index change and design various pruning techniques to further accelerate the index maintenance. Finally, we extend our algorithms to batch mode for shared computation, extend to structural maintenance for full types of update, and generalize to all kinds of TDHL. Our experimental results validate the superiority of our proposals over existing solutions on both index maintenance and query processing.

The issue of ensuring performance with a minimum mass of electrical machines is a task for designing traction electric motors. This article discusses ways to increase the flux linkage and one of the most effective ways is to increase the flux linkage by increasing the rotational speed, since, unlike other methods, this method does not increase the phase resistance and, accordingly, the energy loss in the winding. The main energy losses in an electric machine and the influence of the rotor speed on energy losses are also analysed. Therefore, knowing the losses in the electric machine, the efficiency of the electric machine was calculated. As a result of the study, it was revealed that an increase in the rotational speed leads to a decrease in mass and dimensions, but to a decrease in the efficiency of an electric machine. The optimal values of the rotational speed must be determined for each electric machine, thereby ensuring high efficiency, minimum weight and dimensions, as well as providing the necessary traction and dynamic performance.

The task of finding the optimal shortest path is a key task in routing, and new drivers of the development of data transmission technologies require improvements in devices, services and technologies, in particular, in order to adapt existing algorithms and methods for finding shortest paths for segment routing problems. In this case, the key element of determining the shortest path is the metric. Since determining the shortest paths is an important step in forming a composite path within segment routing, determining the correct metric has a strong impact on this process. Segment routing represents an important evolutionary step forward in the design, management and operation of modern transport networks, including the global Internet. This paper considers the possibility of determining the optimal paths between two arbitrary nodes in a composite network using the segment routing methodology. Discusses the relevance of the problem, the issues of determining the minimum path weight, the path with the minimum weight, achieving the minimum delay, determination of the shortest path with segmentation and the problem of the minimum delay path in the segment routing.

The shortest path-searching with the minimal weight for multiple destinations is a crucial need in an indoor applications, especially in supermarkets, warehouses, libraries, etc. However, when it is used for multiple item searches, its weight becomes higher as it searches only the shortest path between the single sources to each destination item separately. If the conventional Dijkstra algorithm is modified to multi-destination mode then the weight is decreased, but the output path is not considered as the real shortest path among multiple destinations items. Our proposed algorithm is more efficient for finding the shortest path among multiple destination items with minimum weight, compared to the single source single destination and modified multi-destinations of Dijkstra’s algorithm. In this research, our proposed method has been validated by real-world data as well as by simulated random solutions. Our advancement is more applicable in indoor environment applications based on multiple items or destinations searching.

Design optimization of product with the objective of reducing weight is one of current focuses in a product design. In the vehicle industry, in particular, weight reduction has significant impact on vehicle efficiency improvement and the fuel economy. These improvements can have direct impact on operating costs of the vehicle. The methods used to weight reduction are by optimizing the products parameters and by replacing conventional materials with highly sustainable materials strengths. In this paper, design model of existing master leaf spring has been created and optimized using SolidWorks parametric optimization with a goal of reducing the weight of leaf spring, improving the life span of structure by reducing stress and increasing the natural frequency of the leaf spring. The constraint used was limiting stress and natural frequency with the leaf spring’s thickness and width as optimization variables. Optimum values of these parameters of the leaf spring were obtained. Again, using parametrically optimized leaf spring model static and modal analysis was studied under two different composite materials, Epoxy Carbon UD Prepreg and Epoxy E-Glass UD, aiming to get minimum weight and improved life span compared to steel material (55SiMn90). The result shows that the leaf spring of composite materials performed better in terms of the stress level, stiffness and the natural frequency. At the same time, the weight of the composite leaf spring has significantly reduced. In summary, the study concluded that composite leaf spring is better efficient compared with conventional leaf spring from steel.

When Flash memory is used to store the deep neural network (DNN) weights, inference accuracy can degrade due to the Flash memory state errors. To protect the weights from the state errors, the existing methods relied on ECC(Error Correction Code) or parity, which can incur power/storage overhead. In this study, we propose a weight bit inversion method that minimizes the accuracy loss due to the Flash memory state errors without using the ECC or parity. The method first applies WISE(Weight-bit Inversion for State Elimination) that removes the most error-prone state from MLC NAND, thereby improving both the error robustness and the MSB page read speed. If the initial accuracy loss due to weight inversion of WISE is unacceptable, we apply WISER(Weight-bit Inversion for State Error Reduction) that reduces weight mapping to the error-prone state with minimum weight value changes. The simulation results show that after 16K program-erase cycles in NAND Flash, WISER reduces CIFAR-100 accuracy loss by 2.92X for VGG-16 compared to the existing methods.

The storage unit of the system for receiving and converting information for a promising spacecraft has been discussed. The components of this unit, which are power modules, control module, information switching cell, and secondary power supply cell have been described. The design of a special frame from the composition of a storage unit was considered, which serves to install internal and other components in it, ensuring their protection and support of the normal operation. This frame made it possible to provide a wireless connection between power cells and other cells, which together gave the minimum weight and dimensions of the unit. Special attention was paid to the strength and thermal analysis of the block structure. The results of the engineering analysis made it possible to choose the optimal design solutions that ensured the stable operation of the unit and efficient heat removal from the heat-loaded components.

With the development of the Internet of things (IoT), many tasks are automated. The system aims to make the daily tasks of humans in the kitchen easier. This system provides IoT-based Smart Pantry level monitoring using the Internet of things. The containers are fitted with sensors. These are used to gather data about the stock level of items in the container. This data is collected and stored in the cloud. The data is continuously updated. The information includes the changes of weight in regular intervals of time. This system enables a user to view the level of items in a container from any place. The system alerts the user if the container's level goes below minimum weight. It also sends the message to the shopkeeper to place the order of a particular item.

In the energy and aeronautics industry, some components need to be very light but with high strength. For instance, turbine blades and structural components under rotational centrifugal forces, or internal supports, ask for low weight, and in general, all pieces in energy turbine devices will benefit from weight reductions. In space applications, a high ratio strength/weight is even more important. Light components imply new optimal design concepts, but to be able to be manufactured is the real key enable technology. Additive manufacturing can be an alternative, applying radical new approaches regarding part design and components’ internal structure. Here, a new approach is proposed using the replica of a small structure (cell) in two or three orders of magnitude. Laser Powder Bed Fusion (L-PBF) is one of the most well-known additive manufacturing methods of functional parts (and prototypes as well), for instance, starting from metal powders of heat-resistant alloys. The working conditions for such components demand high mechanical properties at high temperatures, Ni-Co superalloys are a choice. The work here presented proposes the use of “replicative” structures in different sizes and orders of magnitude, to manufacture parts with the minimum weight but achieving the required mechanical properties. Printing process parameters and mechanical performance are analyzed, along with several examples. Thanks are owed to H2020-FETOPEN-2018-2019-2020-01 ADAM2 PROJECT Analysis, Design, And Manufacturing using Microstructures and Authors are grateful to Basque government group IT IT1337-19 and the Ministry of Mineco REF DPI2016-74845-R, PID2019-109340RB-I00, KK-2020/00102, KK-2020/00042 and PID2019-104488RB-I00.

A split graph is a graph whose vertex set can be partitioned into a clique and a stable set. Given a graph G and weight function \(w: V(G) \rightarrow \mathbb {Q}_{\ge 0}\), the Split Vertex Deletion (SVD) problem asks to find a minimum weight set of vertices X such that \(G-X\) is a split graph. It is easy to show that a graph is a split graph if and only if it does not contain a 4-cycle, 5-cycle, or a two edge matching as an induced subgraph. Therefore, SVD admits an easy 5-approximation algorithm. On the other hand, for every \(\delta >0\), SVD does not admit a \((2-\delta )\)-approximation algorithm, unless P = NP or the Unique Games Conjecture fails.

We consider the problem of finding patrol schedules for k robots to visit a given set of n sites in a metric space. Each robot has the same maximum speed and the goal is to minimize the weighted maximum latency of any site, where the latency of a site is defined as the maximum time duration between consecutive visits of that site. The problem is NP-hard, as it has the traveling salesman problem as a special case (when \(k=1\) and all sites have the same weight). We present a polynomial-time algorithm with an approximation factor of \(O(k^2 \log \frac{w_{\max }}{w_{\min }})\) to the optimal solution, where \(w_{\max }\) and \(w_{\min }\) are the maximum and minimum weight of the sites respectively. Further, we consider the special case where the sites are in 1D. When all sites have the same weight, we present a polynomial-time algorithm to solve the problem exactly. If the sites may have different weights, we present a 12-approximate solution, which runs in time \((n w_{\max }/w_{\min })^{O(k)}\).

Combinatorics, Coding and Security Group (CCSG) A binary nonlinear code can be represented as a union of cosets of a binary linear subcode. In this paper, the complexity of some algorithms to obtain this representation is analyzed. Moreover, some properties and constructions of new codes from given ones in terms of this representation are described. Algorithms to compute the minimum distance of binary nonlinear codes, based on known algorithms for linear codes, are also established, along with an algorithm to decode such codes. All results are written in such a way that they can be easily transformed into algorithms, and the performance of these algorithms is evaluated.

The multi-parameter problem of the optimal design of composite sandwich structures with the honeycomb filler has been solved. For this purpose, the optimization process was divided into several stages according to the reasonable levels of significance of the objective function’s parameters, i.e., minimal weight. At the first stage, preliminary analysis of thermal protection coatings of sandwich structures with the honeycomb filler is carried out, the most rational types thereof are found, the values of physical and mechanical characteristics, as well as the optimal ranges of variation and the initial value of the thickness of thermal protection coatings for different sections of the structure, are determined. At the second stage, the task of choosing the optimal relationship of the thickness of the thermal protection coating, height of the honeycomb filler, size of its cell, and thicknesses of bearing skins is solved, with simultaneous securing of the acceptable temperature ranges for the outer and inner surfaces of sandwich shells and bearing capacity of the rational variant in all critical areas. To further reduce the weight, the honeycomb filler structure is optimized at the third stage by varying the angle of opening of the cell of irregular hexagonal shape and coefficient of its shape in each section of the structure. Implementation of the suggested approach in weight optimization of a real object’s structural parameters showed its efficiency, expressed in a significant reduction of the optimal structure’s weight compared to its initial variant.

Recently, the best antenna structures have considered microstrip patch antenna due to their simple construction, low cost, minimum weight, and the fact that they can be effortlessly integrated with circuits. To achieve multi-band operation an antenna is designed with an etching rectangle and circle slot on the surface of the patch to achieve multi-band frequency capabilities in mid-band 5G applications. Inset-fed structure type of fed of all antenna printed and fabricated on the brow of the Rogers RT5880 substrate. Then, prototype structures of the microstrip patch antenna were acquired during the design process until achieving the desired antennas. The antenna_1 achieved tri-band characteristics covering the WiMAX band including 2.51 – 2.55 GHz, WLAN, and S-band including 3.80 – 3.87 GHz and C-and X-band including 6.19 – 6.60 GHz. The antenna_2 gives dual-band characteristics covering C-band and X-band including (6.72 – 7.92 GHz) with a peak under -45 dB suitable for mid-band 5G applications. High impedance bandwidth increases between (70 MHz-1.25 GHz) for wireless applications. The proposed microstrip patch antennas were simulated using CST MWS-2015 and were experimentally tested to verify the fundamental characteristics of the proposed design, it offers multiple-band operation with high stable gain and good directional radiation characteristics results.

In the multiway cut problem we are given a weighted undirected graph \(G=(V,E)\) and a set \(T \subseteq V\) of k terminals. The goal is to find a minimum weight set of edges \(E' \subseteq E\) with the property that by removing \(E'\) from G all the terminals become disconnected. In this paper we present a simple local search approximation algorithm for the multiway cut problem with approximation ratio \(2-\frac{2}{k}\). We present an experimental evaluation of the performance of our local search algorithm and show that it greatly outperforms the isolation heuristic of Dalhaus et al. and it has similar performance as the much more complex algorithms of Calinescu et al., Sharma and Vondrak, and Buchbinder et al. which have the currently best known approximation ratios for this problem.