Abstract: We address a general housing market problem with a set of agents and a set of houses. Each agent has a weak ordinal preference list that allows ties on houses as well as an initial endowment; moreover, each agent wishes to reallocate to a better house on the housing market. In this work, we reduces the complexity of the family of top trading cycles algorithms by selecting a specific house from the preferred set during the trading phase. The rule of construction digraphs is used to select an appropriate house. Based on these digraphs, we propose an extended top trading cycles algorithm with complexity \(O(n^{2} r)\) , where \(n\) is the number of agents and \(r\) is the maximum length of ties in the preference lists. The algorithm complexity is lower than that of the state-of-the-art algorithms. We show that the proposed algorithm is individually rational, Pareto efficient, and strategy-proof. It thus overcomes the limitations of a classic top trading cycles algorithm, and features Pareto efficiency and strategy-proofness on the weak preference domain. PubDate: 2021-04-30

Abstract: We study minmax due-date based on common flow-allowance assignment and scheduling problems on a single machine, and extend known results in scheduling theory by considering convex resource allocation. The total cost function of a given job consists of its earliness, tardiness and flow-allowance cost components. Thus, the common flow-allowance and the actual jobs’ processing times are decision variables, implying that the due-dates and actual processing times can be controlled by allocating additional resource to the job operations. Consequently, our goal is to optimize a cost function by seeking the optimal job sequence, the optimal job-dependent due-dates along with the actual processing times. In all addressed problems we aim to minimize the maximal cost among all the jobs subject to a constraint on the resource consumption. We start by analyzing and solving the problem with position-independent workloads and then proceed to position-dependent workloads. Finally, the results are generalized to the method of common due-window. For all studied problems closed form solutions are provided, leading to polynomial time solutions. PubDate: 2021-04-29

Abstract: A k-plex is a hypergraph with the property that each subset of a hyperedge is also a hyperedge and each hyperedge contains at most \(k+1\) vertices. We introduce a new concept called the k-Wiener index of a k-plex as the summation of k-distances between every two hyperedges of cardinality k of the k-plex. The concept is different from the Wiener index of a hypergraph which is the sum of distances between every two vertices of the hypergraph. We provide basic properties for the k-Wiener index of a k-plex. Similarly to the fact that trees are the fundamental 1-dimensional graphs, k-trees form an important class of k-plexes and have many properties parallel to those of trees. We provide a recursive formula for the k-Wiener index of a k-tree using its property of a perfect elimination ordering. We show that the k-Wiener index of a k-tree of order n is bounded below by \(2 {1+(n-k)k \atopwithdelims ()2} - (n-k) {k+1 \atopwithdelims ()2} \) and above by \(k^2 {n-k+2 \atopwithdelims ()3} - (n-k){k \atopwithdelims ()2}\) . The bounds are attained only when the k-tree is a k-star and a k-th power of path, respectively. Our results generalize the well-known results that the Wiener index of a tree of order n is bounded between \((n-1)^2\) and \({n+1 \atopwithdelims ()3}\) , and the lower bound (resp., the upper bound) is attained only when the tree is a star (resp., a path) from 1-dimensional trees to k-dimensional trees. PubDate: 2021-04-27

Abstract: In this paper, a simple two-agent multi-objective scheduling system for flexible job-shop scheduling problem is proposed and corresponding framework is given. Under the framework, a broadcast communication mechanism with task mark and leader–follower control mode are designed and used to ensure orderly activities among agents. To obtain initial solution and improve it, competition and cooperation strategies are developed. To jump out of the local optimal solution and expend the search space, an adaptive iterative loop solving mechanism is designed. Three commonly used benchmark instance sets are adopted to test the performance of the proposed method. Computation results and comparison analysis with other excellent algorithms demonstrate that it is feasible and effective. PubDate: 2021-04-26

Abstract: We consider the spherical k-means problem with outliers, an extension of the k-means problem. In this clustering problem, all sample points are on the unit sphere. Given two integers k and z, we can ignore at most z points (outliers) and need to find at most k cluster centers on the unit sphere and assign remaining points to these centers to minimize the k-means objective. It has been proved that any algorithm with a bounded approximation ratio cannot return a feasible solution for this problem. Our contribution is to present a local search bi-criteria approximation algorithm for the spherical k-means problem. PubDate: 2021-04-25

Abstract: A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, S is an independent set, then S is an independent dominating set. The independent domination number i(G) of G is the minimum cardinality of an independent dominating set in G. In Goddard and Henning (Discrete Math 313:839–854, 2013) conjectured that if G is a connected cubic graph of order n, then \(i(G) \le \frac{3}{8}n\) , except if G is the complete bipartite graph \(K_{3,3}\) or the 5-prism \(C_5 \, \Box \, K_2\) . Further they construct two infinite families of connected cubic graphs with independent domination three-eighths their order. In this paper, we provide a new family of connected cubic graphs G of order n such that \(i(G) = \frac{3}{8}n\) . We also show that if G is a subcubic graph of order n with no isolated vertex, then \(i(G) \le \frac{1}{2}n\) , and we characterize the graphs achieving equality in this bound. PubDate: 2021-04-24

Abstract: Thinning is a frequently used technique capable of producing all kinds of skeleton-like shape features in a topology-preserving way. It is an iterative object reduction: some border points of binary objects that satisfy some topological and geometrical constraints are deleted, and the entire process is repeated until stability is reached. In the conventional implementation of thinning algorithms, the deletability of all border points in the actual picture is to be investigated. That is why, we introduced the concept of k-attempt thinning ( \(k\ge 1\) ) in our previous work (presented in the 20th International Workshop on Combinatorial Image Analysis, IWCIA 2020). In the case of a k-attempt algorithm, if a border point ‘survives’ at least k successive iterations, it is ‘immortal’ (i.e., it cannot be deleted later). In this paper, we give a computationally efficient implementation scheme for 1-attempt thinning, and a 1-attempt 2D parallel thinning algorithm is reported. The advantage of the new implementation scheme over the conventional one is also illustrated. PubDate: 2021-04-24

Abstract: A graph G on n vertices is called non-universal if its maximum degree is at most \(n-2\) . In this paper, we give a structural characterization for non-universal maximal planar graphs with diameter two. In precise, we find 10 basic graphs, and then generate all 25 non-universal maximal planar graphs with diameter two by adding repeatedly and appropriately 3-vertices to some of these 10 basic graphs. As an application, we show that maximal planar graphs with diameter two are pancyclic except five special graphs. PubDate: 2021-04-23

Abstract: Target traversing is an important research topic in wireless sensor networks, with most studies examining coverage issues of the target’s moving paths. The best coverage path is one that minimizes the target support to the sensors. Most existing algorithms either ensure that the target remains as close as possible to the sensors or deploy sensors to enhance coverage. In this paper, we consider a scenario where the target must traverse the sensor network within a certain time constraint. Furthermore, we propose some algorithms to ensure that the target stays close to the sensors within this time constraint. Simulations show that the proposed algorithms can solve traversal path problems in wireless sensor networks. PubDate: 2021-04-22

Abstract: In this paper, we study Roman {k}-dominating functions on a graph G with vertex set V for a positive integer k: a variant of {k}-dominating functions, generations of Roman \(\{2\}\) -dominating functions and the characteristic functions of dominating sets, respectively, which unify classic domination parameters with certain Roman domination parameters on G. Let \(k\ge 1\) be an integer, and a function \(f:V \rightarrow \{0,1,\dots ,k\}\) defined on V called a Roman \(\{k\}\) -dominating function if for every vertex \(v\in V\) with \(f(v)=0\) , \(\sum _{u\in N(v)}f(u)\ge k\) , where N(v) is the open neighborhood of v in G. The minimum value \(\sum _{u\in V}f(u)\) for a Roman \(\{k\}\) -dominating function f on G is called the Roman \(\{k\}\) -domination number of G, denoted by \(\gamma _{\{Rk\}}(G)\) . We first present bounds on \(\gamma _{\{Rk\}}(G)\) in terms of other domination parameters, including \(\gamma _{\{Rk\}}(G)\le k\gamma (G)\) . Secondly, we show one of our main results: characterizing the trees achieving equality in the bound mentioned above, which generalizes M.A. Henning and W.F. klostermeyer’s results on the Roman {2}-domination number (Henning and Klostermeyer in Discrete Appl Math 217:557–564, 2017). Finally, we show that for every fixed \(k\in \mathbb {Z_{+}}\) , associated decision problem for the Roman \(\{k\}\) -domination is NP-complete, even for bipartite planar graphs, chordal bipartite graphs and undirected path graphs. PubDate: 2021-04-22

Abstract: In this paper, a basic dynamic model of the supply chain system is constructed in which the oscillation problems caused by the time delay in remanufacturing, ordering, the disturbance of the system parameters are considered along with the customers’ demand estimation. Time delay in production systems affects the efficiency of supply chain and lead to the bullwhip effect. This paper proposes a new method according to the model structure for controlling the bullwhip effect based on state dependent Riccati equation (ESDRE) and designing suboptimal sliding manifolds for a nonlinear supply chain in the presence of input and state delays. A switching control scheme is obtained based on the designed suboptimal sliding manifold. It is proved that this control scheme can guarantee that the nonlinear supply chain system is asymptotically stable and understand soft switching among subsystems of the nonlinear supply chain to mitigate fluctuations in the system variables. The efficiency of suboptimal sliding manifold method was examined by comparing LQR method in the presence of various time delays. Also, simulation investigation in real supply chain proved this efficiency. PubDate: 2021-04-21

Abstract: The spherical k-means problem (SKMP) is an important variant of the k-means clustering problem (KMP). In this paper, we consider the SKMP, which aims to divide the n points in a given data point set \({\mathcal {S}}\) into k clusters so as to minimize the total sum of the cosine dissimilarity measure from each data point to their respective closest cluster center. Our main contribution is to design an expected constant approximation algorithm for the SKMP by integrating the seeding algorithm for the KMP and the local search technique. By utilizing the structure of the clusters, we further obtain an improved LocalSearch++ algorithm involving \(\varepsilon k\) local search steps. PubDate: 2021-04-20

Abstract: Given a graph G and a digraph D whose vertices are the edges of G, we investigate the problem of finding a spanning tree of G that satisfies the constraints imposed by D. The restrictions to add an edge in the tree depend on its neighborhood in D. Here, we generalize previously investigated problems by also considering as input functions \(\ell \) and u on E(G) that give a lower and an upper bound, respectively, on the number of constraints that must be satisfied by each edge. The produced feasibility problem is denoted by G-DCST, while the optimization problem is denoted by G-DCMST. We show that G-DCST is \(\texttt {NP}\) -complete even if functions \(\ell \) and u are taken under tight assumptions, as well as G and D. On the positive side, we prove two polynomial results, one for G-DCST and another for G-DCMST, and also give a simple exponential-time algorithm along with a proof that it is asymptotically optimal under the ETH. Finally, we prove that other previously studied constrained spanning tree (CST) problems can be modeled within our framework, namely, the Conflict CST, the Forcing CST, the At Least One/All Dependency CST, the Maximum Degree CST, the Minimum Degree CST, and the Fixed-Leaves Minimum Degree CST. PubDate: 2021-04-19

Abstract: The complete bipartite graph \(K_{1,3}\) is called a claw. A graph is said to be claw-free if it contains no induced subgraph isomorphic to a claw. Given a graph G, the NP-hard Graph Declawing Problem (GDP) consists of finding a minimum set \(S\subseteq V(G)\) such that \(G-S\) is claw-free. This work develops a polyhedral study of the GDP polytope, expliciting its full dimensionality, proposing and testing five families of facets: trivial inequalities, claw inequalities, star inequalities, lantern inequalities, and binary star inequalities. In total, four Branch-and-Cut algorithms with separation heuristics have been developed to test the computational benefits of each proposed family on random graph instances and random interval graph instances. Our results show that the model that uses a separation heuristics proposed for star inequalities achieves better results on both set of instances in almost all cases. PubDate: 2021-04-19

Abstract: We consider a Two-Bar Charts Packing Problem (2-BCPP), in which it is necessary to pack two-bar charts (2-BCs) in a unit-height strip of minimum length. The problem is a generalization of the Bin Packing Problem. Earlier, we proposed an \(O(n^2)\) –time algorithm that constructs the packing of n arbitrary 2-BCs, whose length is at most \(2\cdot OPT+1\) , where OPT is the minimum packing length. This paper proposes two new 3/2–approximate algorithms based on sequential matching. One has time complexity \(O(n^4)\) and is applicable when at least one bar of each 2-BC is greater than 1/2. Another has time complexity \(O(n^{3.5})\) and is applicable when, additionally, all BCs are non-increasing or non-decreasing. We prove the estimate’s tightness and conduct a simulation to compare the constructed packings with the optimal solutions or a lower bound of optimum. PubDate: 2021-04-18

Abstract: Let G(V, E) be a simple, connected and undirected graph. A dominating set \(S \subseteq V\) is called a 2-secure dominating set (2-SDS) in G, if for each pair of distinct vertices \(v_1,v_2 \in V\) there exists a pair of distinct vertices \(u_1,u_2 \in S\) such that \(u_1 \in N[v_1]\) , \(u_2 \in N[v_2]\) and \((S {\setminus } \{u_1,u_2\}) \cup \{v_1,v_2 \}\) is a dominating set in G. The size of a minimum 2-SDS in G is said to be 2-secure domination number denoted by \(\gamma _{2s}(G)\) . The 2-SDM problem is to check if an input graph G has a 2-SDS S, with \( \vert S \vert \le k\) , where \( k \in \mathbb {Z}^+ \) . It is proved that for bipartite graphs 2-SDM is NP-complete. In this paper, we prove that the 2-SDM problem is NP-complete for planar graphs and doubly chordal graphs, a subclass of chordal graphs. We reinforce the existing NP-complete result for bipartite graphs, by proving 2-SDM is NP-complete for some subclasses of bipartite graphs specifically, comb convex bipartite and star convex bipartite graphs. We prove that this problem is linear time solvable for bounded tree-width graphs. We also show that the 2-SDM is W[2]-hard even for split graphs. The M2SDS problem is to find a 2-SDS of minimum size in the given graph. We give a \( \varDelta +1 \) -approximation algorithm for M2SDS, where \( \varDelta \) is the maximum degree of the given graph and prove that M2SDS cannot be approximated within \( (1 - \epsilon ) \ln (\vert V \vert ) \) for any \( \epsilon > 0 \) unless \( NP \subseteq DTIME(\vert V \vert ^{ O(\log \log \vert V \vert )}) \) . Finally, we prove that the M2SDS is APX-complete for graphs with \(\varDelta =4.\) PubDate: 2021-04-16

Abstract: The concept of rainbow disconnection number of graphs was introduced by Chartrand et al. (2018). Inspired by this concept, we put forward the concepts of rainbow vertex-disconnection and proper disconnection in graphs. In this paper, we first show that it is NP-complete to decide whether a given edge-colored graph G has a proper edge-cut separating two specified vertices, even though the graph G has \(\Delta (G)=4\) or is bipartite. Then, for a graph G with \(\Delta (G)\le 3\) we show that \(pd(G)\le 2\) and distinguish the graphs with \(pd(G)=1\) and 2, respectively. We also show that it is NP-complete to decide whether a given vertex-colored graph G is rainbow vertex-disconnected, even though the graph G has \(\Delta (G)=3\) or is bipartite. PubDate: 2021-04-16

Abstract: The total proper connection number of a given digraph D, represented by \(\overrightarrow{tpc}(D)\) , denotes the smallest number of colors needed for making D total proper connected. The strong total proper connection number of D, represented by \(\overrightarrow{stpc}(D)\) , shows the smallest number of colors required for making D strong total proper connected. In the present work, we represent some preliminary findings on \(\overrightarrow{tpc}(D)\) and \(\overrightarrow{stpc}(D)\) . Moreover, findings on the (strong) total proper connection numbers of biorientations of graphs, circle digraphs, circulant digraphs and cacti digraphs are provided. PubDate: 2021-04-16

Abstract: The combination of persistent homology and discrete Morse theory has proven very effective in visualizing and analyzing big and heterogeneous data. Indeed, topology provides computable and coarse summaries of data independently from specific coordinate systems and does so robustly to noise. Moreover, the geometric content of a discrete gradient vector field is very useful for visualization purposes. The specific case of multivariate data still demands for further investigations, on the one hand, for computational reasons, it is important to reduce the necessary amount of data to be processed. On the other hand, for analysis reasons, the multivariate case requires the detection and interpretation of the possible interdepedance among data components. To this end, in this paper we introduce and study a notion of perfectness for discrete gradient vector fields with respect to multi-parameter persistent homology, called relative-perfectness. As a natural generalization of usual perfectness in Morse theory for homology, relative-perfectness entails having the least number of critical cells relevant for multi-parameter persistence. As a first contribution, we support our definition of relative-perfectness by generalizing Morse inequalities to the filtration structure where homology groups involved are relative with respect to subsequent sublevel sets. In order to allow for an interpretation of critical cells in 2-parameter persistence, our second contribution consists of two inequalities bounding Betti tables of persistence modules from above and below, via the number of critical cells. Our last result is the proof that existing algorithms based on local homotopy expansions allow for efficient computability over simplicial complexes up to dimension 2. PubDate: 2021-04-13

Abstract: Sets of straight line segments with special structures and properties appear in various applications of geometric modeling, such as scientific visualization, computer-aided design, and medical image processing. In this paper, we derive sharp upper and lower bounds on the number of intersection points and closed regions that can occur in sets of line segments with certain structure, in terms of the number of segments. In particular, we consider sets of segments whose underlying planar graphs are Halin graphs, cactus graphs, maximal planar graphs, and triangle-free planar graphs, as well as randomly produced segment sets. PubDate: 2021-04-10