Search

We study the combinatorial FIFO Stack-Up problem. In the delivery industry, bins have to be moved from conveyor belts onto pallets. Given is a list Q of k sequences of labeled bins and a positive integer p. The goal is to palletize the bins by iteratively removing the first bin of one of the k sequences and putting it onto a pallet located at one of p stack-up places. Each of these pallets has to contain bins of only one label, bins of different labels have to be placed on different pallets. After all bins of one label have been removed from the given sequences, the corresponding stack-up place becomes available for a pallet of bins of another label. The FIFO Stack-Up problem asks whether such a processing is possible. The FIFO Stack-Up problem is known to be NP-complete even if the sequences of Q contain together at most c Q = 6 bins per pallet. This implies that the problem is also hard if all bins of every pallet are distributed to at most d Q = 6 sequences. In this paper we strengthen the hardness to the cases c Q = 5 and d Q = 3. We also show the hardness for the practical case where the number of sequences is smaller than the number of pallets, and we point out differences to related problems like 3D Bin Packing and Train Marshalling. [ABSTRACT FROM AUTHOR]

In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to accomplish this task. Several variants of Graph Searching have been studied mainly because of their close relationship with the pathwidth of a graph. In this paper, we study the complexity of the Exclusive Graph Searching variant. We show that the problem is NP-hard in planar graphs and it can be solved in linear-time in the class of cographs. We also show that monotone Exclusive Graph Searching is NP-complete in split graphs where Pathwidth is known to be solvable in polynomial time. Moreover, we prove that monotone Exclusive Graph Searching is in P in a subclass of star-like graphs where Pathwidth is known to be NP-hard. [ABSTRACT FROM AUTHOR]

We consider a bicriterion generalization of the pathwidth problem: given integers k , l and a graph G , does there exist a path decomposition of G of width at most k and length (i.e., number of bags) at most l ? We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter tractable with respect to k , the generalized problem is NP-complete for any fixed k ≥ 4 , and also for any fixed l ≥ 2 . On the other hand, we give a polynomial-time algorithm that constructs a minimum-length path decomposition of width at most k ≤ 3 for any disconnected input graph. As a by-product, we obtain an almost complete classification for connected graphs: the problem is NP-complete for any fixed k ≥ 5 , and polynomial for any k ≤ 3 . [ABSTRACT FROM AUTHOR]

As technology advances and the spreading of wireless devices grows, the establishment of interconnection networks is becoming crucial. Main activities that involve most of the people concern retrieving and sharing information from everywhere. In heterogeneous networks, devices can communicate by means of multiple interfaces. The choice of the most suitable interfaces to activate (switch-on) at each device results in the establishment of different connections. A connection is established when at its endpoints the devices activate at least one common interface. Each interface is assumed to consume a specific percentage of energy for its activation. This is referred to as the cost of an interface. Due to energy consumption issues, and the fact that most of the devices are battery powered, special effort must be devoted to suitable solutions that prolong the network lifetime. In this paper, we consider the so-called p-Coverage problem where each device can activate at most p of its available interfaces in order to establish all the desired connections of a given network of devices. As the problem has been shown to be NP -hard even for p = 2 and unitary costs of the interfaces, algorithmic design activities have focused in particular topologies where the problem is optimally solvable. Following this trend, we first show that the problem is polynomially solvable for graphs (modeling the underlying network) of bounded treewidth by means of the Courcelle's theorem. Then, we provide two optimal polynomial time algorithms to solve the problem in two subclasses of graphs with bounded treewidth that are graphs of bounded pathwidth and graphs of bounded carvingwidth. The two solutions are obtained by means of dynamic programming techniques. [ABSTRACT FROM AUTHOR]