Search

This paper addresses the problem of determining all optimal integer solutions of a linear integer network flow problem, which we call the all optimal integer flow (AOF) problem. We derive an O (F (m + n) + m n + M) time algorithm to determine all F many optimal integer flows in a directed network with n nodes and m arcs, where M is the best time needed to find one minimum cost flow. We remark that stopping Hamacher's well-known method for the determination of the K best integer flows (Hamacher, 1995) at the first sub-optimal flow results in an algorithm with a running time of O (F m (n log n + m) + M) for solving the AOF problem. Our improvement is essentially made possible by replacing the shortest path sub-problem with a more efficient way to determine a so-called proper zero cost cycle using a modified depth-first search technique. As a byproduct, our analysis yields an enhanced algorithm to determine the K best integer flows that runs in O (K n 3 + M). Besides, we give lower and upper bounds for the number of all optimal integer and feasible integer solutions. Our bounds are based on the fact that any optimal solution can be obtained by an initial optimal tree solution plus a conical combination of incidence vectors of all induced cycles with bounded coefficients. [ABSTRACT FROM AUTHOR]

Lattice problems are algorithmic problems for lattices, whose hardness assures the security of lattice-based cryptography. Given a basis of a lattice, the goal of lattice basis reduction is to seek a new basis of the same lattice whose basis vectors are relatively short and nearly orthogonal to each other. Such reduction algorithms give a fundamental tool to solve lattice problems such as the shortest and the closest vector problems. In this paper, we provide a new self-dual variant of the DeepBKZ reduction algorithm. Our variant dynamically switches performing primal and dual reductions for local blocks of an input basis to effectively reduce the whole basis. In particular, we introduce a parameter of free dimensions to determine the sizes of local blocks to be reduced. We also implement our self-dual DeepBKZ to report its experimental results for random lattice bases. [ABSTRACT FROM AUTHOR]

A dominating set D of a graph G is a set of vertices such that any vertex in G is in D or its neighbor is in D. Enumeration of minimal dominating sets in a graph is one of the central problems in enumeration study since enumeration of minimal dominating sets corresponds to the enumeration of minimal hypergraph transversals. The output-polynomial time enumeration of minimal hypergraph transversals is an interesting open problem. On the other hand, enumeration of dominating sets including non-minimal ones has not been received much attention. In this paper, we address enumeration problems for dominating sets from sparse graphs which are degenerate graphs and graphs with large girth, and we propose two algorithms for solving the problems. The first algorithm enumerates all the dominating sets for a k -degenerate graph in O k time per solution using O n + m space, where n and m are respectively the number of vertices and edges in an input graph. That is, the algorithm is optimal for graphs with constant degeneracy such as trees, planar graphs, H -minor free graphs with some fixed H. The second algorithm enumerates all the dominating sets in constant time per solution for input graphs with girth at least nine. [ABSTRACT FROM AUTHOR]

In this paper we introduce the Ameso optimization problem, a special class of discrete optimization problems. We establish its basic properties and investigate the relation between Ameso optimization and the convex optimization. Further, we design an algorithm to solve a multi-dimensional Ameso problem by solving a sequence of one-dimensional Ameso problems. Finally, we demonstrate how the knapsack problem can be solved using the Ameso optimization framework. [ABSTRACT FROM AUTHOR]

This work presents efficient solutions to several basic algorithmic problems regarding periodicity of partial words. In the first part of the paper, we show that all periods of a partial word of length n are determined in O ( n log n ) time. Moreover, we define algorithms and data structures that help us answer in constant time queries regarding the periodicity of a word’s factors. For these we need an O ( n 2 ) preprocessing time and an O ( n ) updating time, whenever the words are extended by adding a letter. In the second part of the paper, we show that identifying a way to construct a periodic partial word by substituting the letters on some positions of a full word w with holes, where the distance between two consecutive holes must be greater than a given number, can be done in optimal time O ( | w | ) . We also show that identifying a substitution which replaces the minimum number of positions by holes can be done as fast as in the previous case. [ABSTRACT FROM AUTHOR]

Abstract: This paper considers the problem of assigning independent jobs to identical parallel machines with nonsimultaneous starting times. The algorithm MULTIFIT has been applied for the problem but its tight worst-case performance ratio has been unknown. In this paper we prove that the exact performance ratio of MULTIFIT is . [Copyright &y& Elsevier]

Abstract: In this paper 1 [1] The extended abstract of this paper appeared on PPAM 2009, LNCS 6067 (2010) 11–20. we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number ( ) for bipartite graphs , and we prove that holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic bipartite graphs. We also study the problem for bipartite graphs with and we show that 5-coloring is easy and 6-coloring is hard ( -complete). Moreover, we construct an time optimal algorithm for trees. [Copyright &y& Elsevier]

Abstract: The Single-Allocation Ordered Median Hub Location problem is a recent hub model introduced by Puerto et al. (2011) [32] that provides a unifying analysis of the class of hub location models. Indeed, considering ordered objective functions in hub location models is a powerful tool in modeling classic and alternative location paradigms, that can be applied with success to a large variety of problems providing new distribution patterns induced by the different users’ roles within the supply chain network. In this paper, we present a new formulation for the Single-Allocation Ordered Median Hub Location problem and a branch-and-bound-and-cut (B&B&Cut) based algorithm to solve optimally this model. A simple illustrative example is discussed to demonstrate the technique, and then a battery of test problems with data taken from the AP library are solved. The paper concludes that the proposed B&B&Cut approach performs well for small to medium sized problems. [Copyright &y& Elsevier]

In [Secure domination in proper interval graphs, Discrete Applied Mathematics 247 (2018) 70–76], Araki and Miyazaki proposed a linear-time algorithm for finding the secure domination number of proper interval graphs. However, the example they provided is exactly a counterexample. Based on their main idea, we propose a new simple algorithm for solving this problem in this paper. [ABSTRACT FROM AUTHOR]

This paper deals with optimization problems on rotagraphs and fasciagraphs. These graphs are repetitive structures that generalize grids and toroidal grids, respectively. We develop a theoretical framework and get linear-time and constant-time generic algorithms for wide classes of combinatorial problems which are defined in a purely combinatorial way. These classes of problems include in particular many classical optimization problems that are NP-complete in general. Our results unify in a single framework many results of the literature, in particular on the topic of domination–and its variants–in grids. [ABSTRACT FROM AUTHOR]

A many-to-many k -disjoint path cover ( k -DPC for short) of a graph G joining the pairwise disjoint vertex sets S and T , each of size k , is a collection of k vertex-disjoint paths between S and T , which altogether cover every vertex of G . This is classified as paired , if each vertex of S must be joined to a specific vertex of T , or unpaired , if there is no such constraint. In this paper, we develop a linear-time algorithm for the Unpaired DPC problem of finding an unpaired DPC joining S and T given in a unit interval graph, to which the One-to-One DPC and the One-to-Many DPC problems are reduced in linear time. Additionally, we show that the Paired k - DPC problem on a unit interval graph is polynomially solvable for any fixed k . [ABSTRACT FROM AUTHOR]

A vertex subset C of a connected graph G is called a connected k -path vertex cover ( C V C P k ) if every path on k vertices contains at least one vertex from C , and the subgraph of G induced by C is connected. This concept originated in the field of security and supervisory control. This paper studies the minimum (weight) C V C P k problem. We first show that the minimum weight C V C P k problem can be solved in time O ( n ) when the graph is a tree, and can be solved in time O ( r n ) when the graph is a uni-cyclic graph whose unique cycle has length r , where n is the number of vertices. Making use of the algorithm on trees, we present a k -approximation algorithm for the minimum (cardinality) C V C P k problem under the assumption that the graph has girth at least k . An example is given showing that performance ratio k is asymptotically tight for our algorithm. [ABSTRACT FROM AUTHOR]

We consider the problem of decontaminating an infected network using as few mobile cleaning agents as possible and avoiding recontamination. After a cleaning agent has left a vertex v , this vertex will become recontaminated if m or more of its neighbors are infected, where m ≥ 1 is a threshold parameter of the system indicating the local immunity level of the network. This network decontamination problem, also called monotone connected graph search and intruder capture , has been extensively studied in the literature when m = 1 (no immunity). In this paper, we extend these investigations and consider for the first time the network decontamination problem when the parameter m is an arbitrary integer value m ≥ 1 . We direct our study to widely used interconnection networks, namely meshes, tori, and trees. For each of these classes of networks, we present decontamination algorithms with threshold m ; these algorithms work even in asynchronous setting, either directly or with a simple modification requiring one additional agent. We also establish general lower bounds on the number of agents necessary for decontamination with immunity m ; these bounds are tight in the case of trees, while large gaps still exist in the case of meshes and tori. [ABSTRACT FROM AUTHOR]

With the proliferation of multi-gantry automated stacking cranes, the already difficult crane scheduling problem in container terminals has become even more challenging. In this paper we present an efficient algorithm that can solve a sub-problem that arises in this context, namely the prioritization of crane gantry movements once transportation tasks have been assigned. We tackle this problem for both, twin crane setting and crossover crane setting, and develop graphical models and strongly polynomial algorithms accordingly. A series of experiments is carried out where it is shown that the method can produce optimum solutions with exceptionally small run times. [ABSTRACT FROM AUTHOR]

The average eccentricity e c c ( G ) of a graph G is the mean value of eccentricities of all vertices of G . In this paper, we continue the work of Ilić (2012) and resolve a conjecture, obtained by the system AutoGraphiX, about the upper bound on the sum of the average eccentricity and the domination number among connected graphs on n vertices. [ABSTRACT FROM AUTHOR]

A subset F of vertices of a graph G is called a vertex cover P t ( V C P t ) set if every path of order t in G contains at least one vertex from F . The vertex cover P t ( V C P t ) problem is to find a minimum V C P t set in a graph. The V C P t problem is NP-complete for any integer t ≥ 2 . In this paper, we restrict our attention to the V C P 4 problem and present an FPT algorithm with runtime O ∗ ( 3 k ) for the V C P 4 problem. The algorithm constructs a V C P 4 set of size at most k in a given graph G , or reports that no such V C P 4 set exists in G . [ABSTRACT FROM AUTHOR]

A dominating induced matching , also called an efficient edge domination , of a graph G = ( V , E ) with n = | V | vertices and m = | E | edges is a subset F ⊆ E of edges in the graph such that no two edges in F share a common endpoint and each edge in E ∖ F is incident with exactly one edge in F . It is NP-hard to decide whether a graph admits a dominating induced matching or not. In this paper, we design a 1.146 7 n n O ( 1 ) -time exact algorithm for this problem, improving all previous results. This problem can be redefined as a partition problem that is to partition the vertex set of a graph into two parts I and F , where I induces an independent set (a 0-regular graph) and F induces a perfect matching (a 1-regular graph). After giving several structural properties of the problem, we show that the problem always contains some “good vertices,” branching on which by including them to either I or F we can effectively reduce the graph. This leads to a fast exact algorithm to this problem. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of designing in-place algorithms for finding the maximum clique in the intersection graphs of axis-parallel rectangles and disks in R 2 . First, we propose an O ( n 2 log n ) time in-place algorithm for finding the maximum clique of the intersection graph of a set of n axis-parallel rectangles of arbitrary sizes. For the intersection graph of fixed height rectangles, the time complexity can be slightly improved to O ( n log n + n K ) , where K is the size of the maximum clique. For disk graphs, we consider two variations of the maximum clique problem, namely geometric clique and graphical clique. The time complexity of our algorithm for finding the largest geometric clique is O ( m log n + n 2 ) where m is the number of edges in the disk graph, and it works for disks of arbitrary radii. For graphical clique, our proposed algorithm works for unit disks (i.e., of same radii) and the worst case time complexity is O ( n 2 + m ( n + K 3 ) ) ; m is the number of edges in the unit disk intersection graph and K is the size of the largest clique in that graph. It uses O ( n 3 ) time in-place computation of maximum matching in a bipartite graph, where the vertices are given in an array, and the existence of an edge between a pair of vertices can be checked by an oracle on demand (from problem specification) in O ( 1 ) time. This problem is of independent interest. All these algorithms need O ( 1 ) work space in addition to the input array. [ABSTRACT FROM AUTHOR]

Abstract: For a fixed positive integer , a -tuple total dominating set of a graph is a set such that every vertex of is adjacent to at least vertices in . The -tuple total domination problem is to determine a minimum -tuple total dominating set of . This paper studies -tuple total domination from an algorithmic point of view. In particular, we present a linear-time algorithm for the -tuple total domination problem for graphs in which each block is a clique, a cycle or a complete bipartite graph, which include trees, block graphs, cacti and block-cactus graphs. We also establish NP-hardness of the -tuple total domination problem in undirected path graphs. [Copyright &y& Elsevier]

Abstract: A hypergraph is a set family defined on vertex set . The dual of is the set of minimal subsets of such that for any . The computation of the dual is equivalent to several problems, such as minimal hitting set enumeration of a subset family, generation problem for maximal frequent and minimal infrequent sets, and so on. Although many algorithms have been proposed for the problem, to the best of our knowledge, none of them can work on large-scale input with a large number of minimal hitting sets. In this paper, we propose efficient algorithms for checking the minimality and pruning methods. These algorithms enable us to construct time effective and polynomial space dualization algorithms. The computational experiments show that our algorithms are quite fast even for large-scale input for which existing algorithms do not terminate in a practical time. [Copyright &y& Elsevier]

Abstract: The Nonograms puzzle, also known as Paint by Numbers, is a Japanese logic puzzle. It has been shown that the general problem of solving it is NP-hard. In this paper, we answer several theoretical questions related to the puzzle. In addition, we present a new solver and compare its performance with that of existing solvers. [Copyright &y& Elsevier]

Abstract: A -cocoloring of a graph is a partition of the vertex set of into at most independent sets and at most cliques. It is known that determining the cochromatic number and the split chromatic number, which are respectively the minimum and the minimum such that is -cocolorable, is NP-hard problem. A -graph is a graph such that every subset of at most vertices induces at most distinct ’s. In 2011, Bravo et al. obtained a polynomial time algorithm to decide if a -graph is -cocolorable (Bravo et al., 2011). In this paper, we extend this result by obtaining polynomial time algorithms to decide the -cocolorability and to determine the cochromatic number and the split chromatic number for -graphs for every fixed and for graphs with bounded treewidth. We also obtain a polynomial time algorithm to obtain the maximum -cocolorable subgraph of a -graph for every fixed . All these algorithms are fixed parameter tractable. [Copyright &y& Elsevier]

Abstract: This paper considers the problem of clustering the vertices of a complete edge-weighted graph. The objective is to maximize the sum of the edge weights within the clusters (also called cliques). This so-called Clique Partitioning Problem (CPP) is NP-complete, and has several real-life applications such as groupings in flexible manufacturing systems, in biology, in flight gate assignment, etc. Numerous heuristics and exact approaches as well as benchmark tests have been presented in the literature. Most exact methods use branch and bound with branching over edges. We present tighter upper bounds for each search tree node than those known from the literature, improve the constraint propagation techniques for fixing edges in each node, and present a new branching scheme. The theoretical improvements are reflected by computational tests with real-life data. Although a standard solver delivers best results on randomly generated data, the runtime of the proposed algorithm is very low when being applied to instances on object clustering. [Copyright &y& Elsevier]

Abstract: In this paper we consider a general model for locating a repulsive facility in a bounded polygonal region. In order to have a finite set of candidates for the ordered anti-median problem, the class of strictly convex distances must be restricted. For this case an time algorithm is proposed, where is an uniform bound on the number of intersections of two bisectors. [Copyright &y& Elsevier]

Abstract: Given a capacity, the set of dominating -additive capacities is a convex polytope called the -additive monotone core; thus, it is defined by its vertices. In this paper, we deal with the problem of deriving a procedure to obtain such vertices in the line of the results of Shapley and Ichiishi for the additive case. We propose an algorithm to determine the vertices of the -additive monotone core and we explore the possible translations for the -additive case. [Copyright &y& Elsevier]

Given an edge-weighted tree T and an integer p⩾1, the minmax p-traveling salesmen problem on a tree T asks to find p tours such that the union of the p tours covers all the vertices. The objective is to minimize the maximum of length of the p tours. It is known that the problem is NP-hard and has a (2-2/(p+1))-approximation algorithm which runs in O(pp-1np-1) time for a tree with n vertices. In this paper, we consider an extension of the problem in which the set of vertices to be covered now can be chosen as a subset S of vertices and weights to process vertices in S are also introduced in the tour length. For the problem, we give an approximation algorithm that has the same performance guarantee, but runs in O((p-1)!·n) time. [Copyright &y& Elsevier]

In this paper the classical stable roommates problem is generalized to situations when the two partners in a pair perform different roles. We propose an efficient algorithm to decide the existence of a stable matching in this problem. [Copyright &y& Elsevier]