Search

Abstract: For positive integers , an -labeling of a digraph D is a function f from into the set of nonnegative integers such that if x is adjacent to y in D and if x is of distance two to y in D. Elements of the image of f are called labels. The -labeling problem is to determine the -number of a digraph D, which is the minimum of the maximum label used in an -labeling of D. This paper studies -numbers of digraphs. In particular, we determine -numbers of digraphs whose longest dipath is of length at most 2, and -numbers of ditrees having dipaths of length 4. We also give bounds for -numbers of bipartite digraphs whose longest dipath is of length 3. Finally, we present a linear-time algorithm for determining -numbers of ditrees whose longest dipath is of length 3. [Copyright &y& Elsevier]

A border p of a string x is an enhanced cover of x if the number of positions of x that lie within some occurrence of p is the maximum among all borders of x. (String p is a border of x if p is both a proper prefix and a suffix of x.) In this paper, two more general notions based on enhanced covers are introduced: a k -approximate enhanced cover and a relaxed k -approximate enhanced cover, where a fixed maximum number of errors k under the Hamming distance is considered. The k -approximate enhanced cover of x is its border, and its k -approximate occurrences are also considered in the covered number of positions of x. The relaxed k -approximate enhanced cover of x is a factor of x and a k -approximate border of x. Algorithms that compute all the variations of k -approximate enhanced covers mentioned above are presented in this paper. [ABSTRACT FROM AUTHOR]

In this paper, we study the path version of the Traveling Salesman Problem with the edge cost function satisfying a "relaxed" form of triangle inequality called the biased triangle inequality. We denote this problem as the Biased-TSP-Path. In this paper, we prove that the Biased-TSP-Path is approximable within a constant factor. Specifically, we design a 4-approximation algorithm by a suitable modification of the double-tree algorithm using effective shortcutting procedures. [ABSTRACT FROM AUTHOR]

We consider a community formation problem in social networks, where the users are either friends or enemies. The users are partitioned into conflict-free groups (i.e. , independent sets in the conflict graph G − = (V , E) that represents the enmities between users). The dynamics goes on as long as there exists any set of at most k users, k being any fixed parameter, that can change their current groups in the partition simultaneously , in such a way that they all strictly increase their utilities (number of friends i.e. , the cardinality of their respective groups minus one). Previously, the best-known upper-bounds on the maximum time of convergence were O (| V | α (G −)) for k ≤ 2 and O ( | V | 3) for k = 3 , with α (G −) being the independence number of G −. Our first contribution in this paper consists in reinterpreting the initial problem as the study of a dominance ordering over the vectors of integer partitions. With this approach, we obtain for k ≤ 2 the tight upper-bound O (| V | min { α (G −) , | V | }) and, when G − is the empty graph, the exact value of order (2 | V |) 3 ∕ 2 3. The time of convergence, for any fixed k ≥ 4 , was conjectured to be polynomial (Escoffier et al., 2012; Kleinberg and Ligett, 2013). In this paper we disprove this. Specifically, we prove that for any k ≥ 4 , the maximum time of convergence is in Ω ( | V | Θ (log | V |) ). [ABSTRACT FROM AUTHOR]

A perfect matching in an undirected graph G = (V , E) is a set of vertex disjoint edges from E that include all vertices in V. The perfect matching problem is to decide if G has such a matching. Recently Rothvoß proved the striking result that the Edmonds' matching polytope has exponential extension complexity. In this paper for each n = | V | we describe a polytope for the perfect matching problem that is different from Edmonds' polytope and define a weaker notion of extended formulation. We show that the new polytope has a weak extended formulation (WEF) Q of polynomial size. For each graph G with n vertices we can readily construct an objective function so that solving the resulting linear program over Q decides whether or not G has a perfect matching. With this construction, a straightforward O (n 4) implementation of Edmonds' matching algorithm using O (n 2) bits of space would yield a WEF Q with O (n 6 log n) inequalities and variables. The construction is uniform in the sense that, for each n , a single polytope is defined for the class of all graphs with n nodes. The method extends to solve polynomial time optimization problems, such as the weighted matching problem. In this case a logarithmic (in the weight of the optimum solution) number of optimizations are made over the constructed WEF. The method described in the paper involves the construction of a compiler that converts an algorithm given in a prescribed pseudocode into a polytope. It can therefore be used to construct a polytope for any decision problem in P which can be solved by a well defined algorithm. Compared with earlier results of Dobkin–Lipton–Reiss and Valiant our method allows the construction of explicit linear programs directly from algorithms written for a standard register model, without intermediate transformations. We apply our results to obtain polynomial upper bounds on the non-negative rank of certain slack matrices related to membership testing of languages in P/poly. [ABSTRACT FROM AUTHOR]

Abstract In this paper we consider a variant of the k -separator problem. Given a graph G = (V ∪ T , E) with V ∪ T the set of vertices, where T is a set of k terminals, the multi-terminal vertex separator problem consists in partitioning V ∪ T into k + 1 subsets { S , V 1 , ... , V k } such that there is no edge between two different subsets V i and V j , each V i contains exactly one terminal and the size of S is minimum. In this paper, we first show that the problem is NP-hard. Then we give two integer programming formulations for the problem. For one of these formulations, we investigate the related polyhedron and discuss its polyhedral structure. We describe some valid inequalities and characterize when these inequalities define facets. We also derive separation algorithms for these inequalities. Using these results, we develop a Branch-and-Cut algorithm for the problem, along with an extensive computational study. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we empirically profile three algorithms for the Shortest Negative Cost Cycle (SNCC) problem. In this problem, we are given a directed, weighted graph G = 〈 V , E , c 〉 , and the goal is to identify a negative cost cycle with the fewest number of edges. The SNCC problem finds applications in a number of domains ranging from program verification to certifying algorithm design. The first polynomial time algorithm for this problem was proposed in Subramani (2009). Since then, several additional techniques, including a randomized approach, have been proposed for the SNCC problem. Our goal in this paper is to analyze three algorithmic paradigms for this problem from the empirical perspective. Towards this end, we profile these algorithmic approaches over a wide range of inputs. Our results indicated that the randomized algorithm is the algorithm of choice over a number of graph classes. [ABSTRACT FROM AUTHOR]

Abstract The paper is devoted to a Gram classification of an important class of signed graphs with loops playing an important role in many branches of mathematics, physics and computer science including game theory, crystallography, Diophantine geometry, Lie theory, spectral graph theory, a graph coloring technique, algebraic methods in graph theory. They have many deep applications in spectral machine learning methods, electrical networks, to link sign prediction in signed unipartite and bipartite networks, and community partition in social networks. We continue the study of finite connected edge-bipartite graphs Δ (bigraphs, for short), with m ≥ 2 vertices (a class of signed graphs), started in Simson (2013) and developed in Simson (2016) by means of the non-symmetric Gram matrix G ˇ Δ ∈ M m (Z) defining Δ , its symmetric Gram matrix G Δ : = 1 2 [ G ˇ Δ + G ˇ Δ t r ] ∈ M m (1 2 Z) , and the Gram quadratic form q Δ : Z m → Z. In the present paper, given n ≥ 1 , we mainly study connected principal Cox-regular edge-bipartite graphs Δ with loops and n + 1 ≥ 2 vertices, in the sense that the symmetric Gram matrix G Δ ∈ M n + 1 (Z) of Δ is positive semi-definite of rank n ≥ 1. Our aim is to classify such edge-bipartite graphs by means of an inflation algorithm, up to the weak Gram Z -congruence Δ ∼ Z Δ ′ , where Δ ∼ Z Δ ′ means that G Δ ′ = B t r ⋅ G Δ ⋅ B , for some B ∈ M n + 1 (Z) with det B = ± 1. Our main result of the paper asserts that, given a principal Cox-regular connected edge-bipartite graph Δ with n + 1 ≥ 2 vertices, there exists an edge-bipartite Euclidean graph D n + 1 of Tables A and B, and a suitably chosen sequence t • − of the inflation operators, each of one of the forms Δ ′ ↦ t a − Δ ′ or Δ ′ ↦ t a b − Δ ′ , such that the composite operator Δ ↦ t • − Δ reduces Δ to the bigraph D n + 1 such that: (i) Δ ∼ Z D n + 1 and (ii) the bigraphs Δ , and D n + 1 have the same number of loops. The algorithm does not change loops and computes a matrix B ∈ M n + 1 (Z) , with det B = ± 1 , defining the weak Gram Z -congruence Δ ∼ Z D n + 1 , that is, satisfying the equation G D n + 1 = B t r ⋅ G Δ ⋅ B. [ABSTRACT FROM AUTHOR]

In this paper, we consider the homogeneous m -machine scheduling problem where unit-time jobs have to be scheduled within their time windows so that, for any subset of machines, the set of the time units at which at least one machine is busy, is an interval. For this problem, a time assignment of the jobs satisfying the time windows constraints is a schedule if it has a pyramidal profile and is a k -schedule if this profile property is satisfied up to level k only. We develop a generic algorithm to solve the problem and show it is correct using a proof that mainly relies on a necessary and sufficient condition for a schedule to exist proved in a previous paper. We finally show that the generic algorithm is polynomial. We conclude by giving the directions of ongoing works and by bringing open questions related to different variants of the basic non-idling m -machine scheduling problem. [ABSTRACT FROM AUTHOR]

The boxicity of a graph G ( V , E ) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes in R k . Cubicity is a variant of boxicity, where the axis parallel boxes in the intersection representation are restricted to be of unit length sides. Deciding whether the boxicity (resp. cubicity) of a graph is at most k is NP-hard, even for k = 2 or 3 . Computing these parameters is inapproximable within O ( n 1 − ϵ ) -factor, for any ϵ > 0 in polynomial time unless NP = ZPP , even for many simple graph classes. In this paper, we give a polynomial time κ ( n ) factor approximation algorithm for computing boxicity and a κ ( n ) ⌈ log log n ⌉ factor approximation algorithm for computing the cubicity, where κ ( n ) = 2 n log log n ∕ log n . These o ( n ) factor approximation algorithms also produce the corresponding box (resp. cube) representations. As a special case, this resolves the question posed by Spinrad (2003) about polynomial time construction of o ( n ) dimensional box representations for boxicity 2 graphs. Other consequences of our approximation algorithm include O ( κ ( n ) ) factor approximation algorithms for computing the following parameters: the partial order dimension (poset dimension) of finite posets, the interval dimension of finite posets, minimum chain cover of bipartite graphs, Ferrers dimension of digraphs and threshold dimension of split graphs and co-bipartite graphs. Each of these parameters is inapproximable within an O ( n 1 − ϵ ) -factor, for any ϵ > 0 in polynomial time unless NP = ZPP and the algorithms we derive seem to be the first o ( n ) factor approximation algorithms known for all these problems. We note that obtaining a o ( n ) factor approximation for poset dimension was also mentioned as an open problem by Felsner et al. (2017). In the second part of this paper, parameterized approximation algorithms for boxicity using various edit distance parameters are derived. We also present a parameterized approximation scheme for cubicity, using minimum vertex cover number as the parameter. [ABSTRACT FROM AUTHOR]

In this paper, we study the most basic domination invariants in graphs, in which number 2 is intrinsic part of their definitions. We classify them upon three criteria, two of which give the following previously studied invariants: the weak 2 -domination number, γ w 2 ( G ) , the 2 -domination number, γ 2 ( G ) , the { 2 } -domination number, γ { 2 } ( G ) , the double domination number, γ × 2 ( G ) , the total { 2 } -domination number, γ t { 2 } ( G ) , and the total double domination number, γ t × 2 ( G ) , where G is a graph in which the corresponding invariant is well defined. The third criterion yields rainbow versions of the mentioned six parameters, one of which has already been well studied, and three other give new interesting parameters. Together with a special, extensively studied Roman domination, γ R ( G ) , and two classical parameters, the domination number, γ ( G ) , and the total domination number, γ t ( G ) , we consider 13 domination invariants in graphs. In the main result of the paper we present sharp upper and lower bounds of each of the invariants in terms of every other invariant, a large majority of which are new results proven in this paper. As a consequence of the main theorem we obtain new complexity results regarding the existence of approximation algorithms for the studied invariants, matched with tight or almost tight inapproximability bounds, which hold even in the class of split graphs. [ABSTRACT FROM AUTHOR]

In this paper the following selection problem is discussed. A set of n items is given and we wish to choose a subset of exactly p items of the minimum total cost. This problem is a special case of 0–1 knapsack in which all the item weights are equal to 1. Its deterministic version has an O ( n ) -time algorithm, which consists in choosing p items of the smallest costs. In this paper it is assumed that the item costs are uncertain. Two robust models, namely two-stage and recoverable ones, under discrete and interval uncertainty representations, are discussed. Several positive and negative complexity results for both of them are provided. [ABSTRACT FROM AUTHOR]

A circulant graph C n ( a 1 , … , a k ) is a graph with n vertices { v 0 , … , v n − 1 } such that each vertex v i is adjacent to vertices v ( i + a j ) m o d n , for j = 1 , … , k . In this paper we investigate the vertex colouring problem on circulant graphs. We approach the problem in a purely combinatorial way based on an array representation and propose an exact O ( k 3 log 2 n + n ) algorithm for a subclass of 3-chromatic C n ( a 1 , … , a k ) ’s with k ≥ 2 , which are characterized in the paper. [ABSTRACT FROM AUTHOR]

Many hard graph problems, such as Hamiltonian Cycle, become FPT when parameterized by treewidth, a parameter that is bounded only on sparse graphs. When parameterized by the more general parameter clique-width, Hamiltonian Cycle becomes W[1]-hard, as shown by Fomin et al. (2010). Sæther and Telle address this problem in their paper (Sæther and Telle, 2016) by introducing a new parameter, split-matching-width, which lies between treewidth and clique-width in terms of generality. They show that even though graphs of restricted split-matching-width might be dense, solving problems such as Hamiltonian Cycle can be done in FPT time. Recently, it was shown that Hamiltonian Cycle parameterized by treewidth is in EPT (Bodlaender et al., 2013; Fomin et al., 2014), meaning it can be solved in n O ( 1 ) 2 O ( k ) -time. In this paper, using tools from Fomin et al. (2014), we show that also parameterized by split-matching-width Hamiltonian Cycle is EPT. To the best of our knowledge, this is the first EPT algorithm for any “globally constrained” graph problem parameterized by a non-trivial and non-sparse structural parameter. To accomplish this, we also give an algorithm constructing a branch decomposition approximating the minimum split-matching-width to within a constant factor. Combined, these results show that the algorithms in Sæther and Telle (2016) for Edge Dominating Set, Chromatic Number and Max Cut all can be improved. In fact, using our new approximation algorithm, under the Exponential Time Hypothesis, the Hamiltonian Cycle algorithm of this paper, and the three algorithms for MaxCut, Edge Dominating Set, and Chromatic Number, are asymptotically optimal. [ABSTRACT FROM AUTHOR]

For a connected graph G = ( V ( G ) , E ( G ) ) and two disjoint subsets of V ( G ) A = { α 1 , … , α k } and B = { β 1 , … , β k } , a paired (many-to-many) k -disjoint path cover of G joining A and B is a vertex-disjoint path cover { P 1 , … , P k } such that P i is a path from α i to β i for 1 ≤ i ≤ k . In the recent paper, Park and Ihm (2014) presented a necessary and sufficient condition for a paired 2 -disjoint path cover joining two vertex sets to exist in the cube of a connected graph. In this paper, we propose an O ( | V ( G ) | + | E ( G ) | ) -time algorithm that actually finds such a paired 2 -disjoint path cover. In particular, we show that, in order to build a desired disjoint path cover, it is sufficient to consider only the edges of a carefully selected spanning tree of the graph and at most one additional edge not in the tree, which allows an efficient linear-time algorithm. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithmic framework for some basic problems on binary images. Algorithms for binary images such as one of extracting a connected component containing a query pixel and that of connected components labeling play basic roles in image processing. Those algorithms usually use linear work space for efficient implementation. In this paper we propose algorithms for several basic problems on binary images which are efficient in time and space, using space-efficient algorithms for grid graphs. More exactly, some of them run in O ( n log n ) time using O ( 1 ) work space and the others run in O ( n ) or O ( n log n ) time using O ( n ) work space for a binary image of n pixels stored in a read-only array. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of computing the 2-vertex-connected components of directed graphs. We present a new algorithm for solving this problem in O ( n m ) time. Furthermore, we show that the old algorithm of Erusalimskii and Svetlov runs in O ( n m 2 ) time. In this paper, we investigate the relationship between 2-vertex-connected components and dominator trees. We also consider three applications of our new algorithm, which are approximation algorithms for problems that are generalization of the problem of approximating the smallest 2-vertex-connected spanning subgraph of 2-vertex-connected directed graph. [ABSTRACT FROM AUTHOR]

A graph G = ( V , E ) is a word-representable graph if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if ( x , y ) ∈ E for each x ≠ y . In this paper we give an effective characterization of word-representable graphs in terms of orientations. Namely, we show that a graph is word-representable if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about word-representable graphs, in particular showing that the recognition problem is in NP, and that word-representable graphs include all 3-colorable graphs. We also explore bounds on the size of the word representing the graph. The representation number of G is the minimum k such that G is a representable by a word, where each letter occurs k times; such a k exists for any word-representable graph. We show that the representation number of a word-representable graph on n vertices is at most 2 n , while there exist graphs for which it is n / 2 . [ABSTRACT FROM AUTHOR]

This paper introduces the notion of involution module, the first generalization of the modular decomposition of 2-structures which has a unique linear-sized decomposition tree. We derive an O ( n 2 ) decomposition algorithm and we take advantage of the involution modular decomposition tree to obtain several algorithmic results. It is well-known that cographs (or equivalently P 4 -free graphs) are the graphs that are totally decomposable w.r.t modular decomposition. In a similar way, we introduce the class of switch cographs, as the class of graphs that are totally decomposable w.r.t involution modular decomposition. This class generalizes the class of cographs and appears to be exactly the class of (Bull, Gem, Co-Gem, C 5 )-free graphs. We use our new decomposition tool to design three practical algorithms for the maximum cut, vertex cover and vertex separator problems. The complexity of these problems was still unknown for this class of graphs. This paper also improves the complexity of the maximum clique, the maximum independent set, the chromatic number and the maximum clique cover problems by giving efficient algorithms, thanks to the decomposition tree. Eventually, we show that this class of graphs has clique-width at most 4 and that a clique-width expression can be computed in linear time. [ABSTRACT FROM AUTHOR]

We study the problem of finding in a graph an inclusionwise maximal independent set of minimum cardinality, known as minimum maximal independent set or independent dominating set problem. This is one of the hardest problems in algorithmic graph theory. In particular, restricted to the class of so called SAT-graphs, this problem coincides with satisfiability , the central problem of theoretical computer science. The class of SAT-graphs, and many other important graph classes, such as graphs of bounded vertex degree or line graphs, can be characterized by finitely many forbidden induced subgraphs. We call such classes finitely defined. The paper [R. Boliac and V. Lozin, Independent domination in finitely defined classes of graphs, Theoretical Computer Science, 301 (2003) 271–284] reveals various conditions under which the independent dominating set problem remains NP-hard in a finitely defined class. In the present paper, we identify a number of finitely defined classes where the problem admits polynomial-time solutions. In particular, we prove that the problem is solvable in polynomial time in the class of P 2 + P 3 -free graphs by correcting a mistake of the first two authors of the paper in their earlier solution. This result is in a sharp contrast with the fact that in the class of P 3 + P 3 -free graphs the problem is known to be NP-hard, since this class contains all SAT-graphs. [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]

This paper describes an exact algorithm for a variant of the vehicle routing problem in which customer demands to be collected are stochastic. Demands are revealed upon the vehicle arrival at customer locations. As a result, a vehicle may reach a customer and does not have sufficient capacity to collect the realized demand. Such a situation is referred to as a failure. In this paper the following recourse action is then applied when failure occurs: the vehicle returns to the depot to unload and resumes its planned route at the point of failure. The capacitated vehicle routing problem with stochastic demands (VRPSD) consists of minimizing the sum of the planned routes cost and of the expected recourse cost. The VRPSD is formulated as a two-stage stochastic programming model and solved by means of an integer L -shaped algorithm. This paper introduces three lower bounding functionals based on the generation of general partial routes, as well as an exact separation procedure to identify violated cuts. Extensive computational results confirm the effectiveness of the proposed algorithm, as measured by a substantial reduction in the number of feasible solutions that have to be explicitly eliminated. This translates into a higher proportion of instances solved to optimality, reduced optimality gaps, and lower computing times. [ABSTRACT FROM AUTHOR]

In this paper, we study the Shortest Color Spanning t - Intervals problem, and related generalizations, namely Smallest Color Spanning t - Squares and Smallest Color Spanning t - Circles. The generic setting is the following: we are given n points in the plane (or on a line), each colored with one of k colors. For each color i we also have a demand s i. Given a budget t , we are required to find at most t objects (for example, intervals, squares, circles, etc.) that cover at least s i points of color i. Typically, the goal is to minimize the maximum perimeter or area. We provide exact algorithms for these problems for the cases of intervals, circles and squares, generalizing several known results. In the case of intervals, we provide a comprehensive understanding of the complexity landscape of the problem after taking several natural parameters into account. Given that the problem turns out to be W 1 -hard parameterized by the standard parameters, we introduce a new parameter, namely sparsity, and prove new hardness and tractability results in this context. For squares and circles, we use existing algorithms of one smallest color spanning object in order to design algorithms for getting t identical objects of minimum size whose union spans all the colors. [ABSTRACT FROM AUTHOR]

Edge-Independent spanning trees (EISTs) can be used in IP fast rerouting to guarantee recovery from link failures, as well as in data broadcasting in networks to enhance fault-tolerance, bandwidth, and security. The n -dimensional augmented cube A Q n is an important node-symmetric variant of the n -dimensional hypercube Q n. Recently, Wang et al. proposed a method to construct 2 n − 1 EISTs in A Q n (Wang et al., 2017). However, the height of the tallest EIST is no less than n +2. Since height is an important performance indicator of the EISTs, in this paper, we further study the existence and construction of EISTs in augmented cubes with lower heights. We first propose a constructive algorithm to construct 2 n − 1 trees rooted at any node in A Q n . We then prove the 2 n − 1 trees obtained by the algorithm are 2 n − 1 EISTs with the maximal height n , and the time complexity of the algorithm is O (N log N) , where N = 2 n is the number of nodes in A Q n . [ABSTRACT FROM AUTHOR]

In the paper we introduce and study partitions of vectors in N p , as a natural extension of the classical partitions of integers. We show that these vector partitions are the suitable combinatorial notion in extending the Faà di Bruno formula to a general multi-variable setting, as well as in generalizing Bell polynomials. The Adomian polynomials can be obtained from this framework as a particular case. We also give a recursive algorithm which is proved to generate all the vector partitions without repetitions, and which can be used in numerical applications of extended Faà di Bruno formulae and generalized Bell polynomials. [ABSTRACT FROM AUTHOR]

In 2000, Babson and Steingrímsson generalized the notion of permutation patterns to the so-called vincular patterns, and they showed that many Mahonian statistics can be expressed as sums of vincular pattern occurrence statistics. STAT is one of such Mahonian statistics discovered by them. In 2016, Kitaev and the third author introduced a words analogue of STAT and proved a joint equidistribution result involving two sextuple statistics on the whole set of words with fixed length and alphabet. Moreover, their computer experiments hinted at a finer involution on R (w) , the rearrangement class of a given word w. We construct such an involution in this paper, which yields a comparable joint equidistribution between two sextuple statistics over R (w). Our involution builds on Burstein's involution and Foata–Schützenberger's involution that utilizes the celebrated RSK algorithm. [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]

Abstract: This paper studies a variation of domination in graphs called rainbow domination. For a positive integer , a -rainbow dominating function of a graph is a function such that for any vertex with . The -rainbow domination number of is the minimum value of , where runs over all -rainbow dominating functions of . A related concept is as follows. A weak -dominating function of is a function such that for any vertex with . The weak -domination number of is the minimum value of , where runs over all weak -dominating functions of . In this paper, we prove that for any strongly chordal graph . Our approach is a more general setting called the -function, which leads to interesting results on other variations of domination. We also give a linear-time algorithm for finding the weak -domination numbers of block graphs. [Copyright &y& Elsevier]

Despite the fact that the field of pattern avoiding permutations has been skyrocketing over the last two decades, there are very few exhaustive generating algorithms for such classes of permutations. In this paper we introduce the notions of regular and colored regular set of forbidden patterns, which are particular cases of right-justified sets of forbidden patterns. We show the (colored) regularity of several sets of forbidden patterns (some of them involving variable length patterns) and we derive a general framework for the efficient generation of permutations avoiding them. The obtained generating algorithms are based on succession functions, a notion which is a byproduct of the ECO method introduced in the context of enumeration and random generation of combinatorial objects. For some classes of permutations falling under our general framework, the corresponding counting sequences are classical in combinatorics, such as Pell, Fibonacci, Catalan, Schröder and binomial transform of Padovan sequence. [ABSTRACT FROM AUTHOR]

In this paper we show that the negative sample distance covariance function is a quasi-concave set function of samples of random variables that are not statistically independent. We use these properties to propose greedy algorithms to combinatorially optimize some diversity (low statistical dependence) promoting functions of distance covariance. Our greedy algorithm obtains all the inclusion-minimal maximizers of this diversity promoting objective. Inclusion-minimal maximizers are multiple solution sets of globally optimal maximizers that are not a proper subset of any other maximizing set in the solution set. We present results upon applying this approach to obtain diverse features (covariates/variables/predictors) in a feature selection setting for regression (or classification) problems. We also combine our diverse feature selection algorithm with a distance covariance based relevant feature selection algorithm of Kong et al. (2015) to produce subsets of covariates that are both relevant yet ordered in non-increasing levels of diversity of these subsets. [ABSTRACT FROM AUTHOR]

Given an undirected graph, a minimum cut cover is a collection of cuts covering the whole set of edges and having minimum cardinality. This paper is dedicated to the fractional version of this problem where a fractional weight is computed for each cut such that, for each edge, the sum of the weights of all cuts containing it is no less than 1, while the sum of all weights is minimized. The fractional cover is computed for different graph classes among which are the weakly bipartite graphs. Efficient algorithms are described to compute lower and upper bounds with worst-case performance guarantees. A general randomized approach is also presented giving new insights into Goemans and Williamson's algorithm for the maximum cut problem. Some numerical experiments are included to assess the quality of bounds. [ABSTRACT FROM AUTHOR]

In this paper we provide exponential-time algorithms to enumerate the maximal irredundant sets of chordal graphs and two of their subclasses. We show that the maximum number of maximal irredundant sets of an n -vertex chordal graph is at most 1. 754 9 n , and these can be enumerated in time O (1. 754 9 n). For interval graphs, we achieve the better upper bound of 1. 695 7 n for the number of maximal irredundant sets and we show that they can be enumerated in time O (1. 695 7 n). Finally, we show that an n -vertex forest has at most 1. 618 1 n maximal irredundant sets that can be enumerated in time O (1. 618 1 n). We complement the latter result by providing a family of forests having at least 1. 529 2 n maximal irredundant sets. [ABSTRACT FROM AUTHOR]

In this paper, we study the concept of convex domination in maximal outerplanar graphs. For this class of graphs, we discuss several properties of this domination parameter, in particular, we provide upper bounds on the convex domination number and study effects on the convex domination number when a maximal outerplanar graph is modified by flipping a diagonal. We also propose a linear time algorithm for computing a minimum convex dominating set in a given maximal outerplanar graph. In addition, we consider the concept of convex guard sets in maximal outerplanar graphs and simple polygons. [ABSTRACT FROM AUTHOR]

The scattering number of a graph was introduced by Jung (1978) in relation to hamiltonian properties and network vulnerability, and it can also be regarded as the additive analogue of the toughness introduced by Chvátal. In this paper, we consider the problem of computing a generalized variant, namely the weighted scattering number. In general, computing the scattering number of a graph is NP-hard. Here we investigate the computational complexity of the weighted scattering number and give a polynomial time algorithm for computing this parameter when the input graph is an interval graph. Our results generalize the algorithm given by Broersma et al. (2015) which can only deal with the unweighted case, i.e., the special case when all the vertex weights are equal to 1. [ABSTRACT FROM AUTHOR]

In (k , r) - Center we are given a (possibly edge-weighted) graph and are asked to select at most k vertices (centers), so that all other vertices are at distance at most r from a center. In this paper we provide a number of tight fine-grained bounds on the complexity of this problem with respect to various standard graph parameters. Specifically: • For any r ≥ 1 , we show an algorithm that solves the problem in O ∗ ( (3 r + 1) cw) time, where cw is the clique-width of the input graph, as well as a tight SETH lower bound matching this algorithm's performance. As a corollary, for r = 1 , this closes the gap that previously existed on the complexity of Dominating Set parameterized by cw. • We strengthen previously known FPT lower bounds, by showing that (k , r) - Center is W[1]-hard parameterized by the input graph's vertex cover (if edge weights are allowed), or feedback vertex set, even if k is an additional parameter. Our reductions imply tight ETH-based lower bounds. Finally, we devise an algorithm parameterized by vertex cover for unweighted graphs. • We show that the complexity of the problem parameterized by tree-depth is 2 Θ (td 2) , by showing an algorithm of this complexity and a tight ETH-based lower bound. We complement these mostly negative results by providing FPT approximation schemes parameterized by clique-width or treewidth, which work efficiently independently of the values of k , r. In particular, we give algorithms which, for any ϵ > 0 , run in time O ∗ ( (tw ∕ ϵ) O (tw) ) , O ∗ ( (cw ∕ ϵ) O (cw) ) and return a (k , (1 + ϵ) r) -center if a (k , r) -center exists, thus circumventing the problem's W-hardness. [ABSTRACT FROM AUTHOR]

Given a simple, connected graph, a pebbling configuration (or just configuration) is a function from its vertex set to the nonnegative integers. A pebbling move between adjacent vertices removes two pebbles from one vertex and adds one pebble to the other. A vertex r is said to be reachable from a configuration if there exists a sequence of pebbling moves that places at least one pebble on r. A configuration is solvable if every vertex is reachable. The pebbling number π (G) of a graph G is the minimum integer such that every configuration of size π (G) on G is solvable. A graph G is said to satisfy the two-pebbling property if for any configuration with more than 2 π (G) − q pebbles, where q is the number of vertices with pebbles, two pebbles can be moved to any vertex of G. A Lemke graph is a graph that does not satisfy the two-pebbling property. In this paper we present a new algorithm to determine if a vertex is reachable with a given configuration and if a configuration on a graph is solvable. We also discuss straightforward algorithms to compute the pebbling number and to determine whether or not a graph has the two-pebbling property. Finally, we use these algorithms to determine all Lemke graphs on at most 9 vertices, finding many previously unknown Lemke graphs. [ABSTRACT FROM AUTHOR]

We are interested in the solution of the maximum k -balanced subgraph problem. Let G = (V , E , s) be a signed graph and k a positive scalar. A signed graph is k -balanced if V can be partitioned into at most k sets in such a way that positive edges are found only within the sets and negative edges go between sets. The maximum k -balanced subgraph problem is the problem of finding a subgraph of G that is k -balanced and maximum according to the number of vertices. This problem has applications in clustering problems appearing in collaborative v s conflicting environments. The particular case k = 2 yields the problem of finding a maximum balanced subgraph in a signed graph and its exact solution has been addressed before in the literature. In this paper, we provide a representatives formulation for the general problem and present a partial description of the associated polytope, including the introduction of strengthening families of valid inequalities. A branch-and-cut algorithm is described for finding an optimal solution to the problem. An ILS metaheuristic is implemented for providing primal bounds for this exact method and a branching rule strategy is proposed for the representatives formulation. Computational experiments, carried out over a set of random instances and on a set of instances from an application, show the effectiveness of the valid inequalities and strategies adopted in this work. [ABSTRACT FROM AUTHOR]

Chronological interval digraphs are a natural directed analogue of interval graphs. They admit elegant characterizations as well as efficient recognition algorithms. Recently, a generalization of chronological interval digraphs to 2-dimensional space called chronological rectangle digraphs was introduced and studied. Although many interesting properties of chronological rectangle digraphs have been discovered, the most fundamental question of whether this class of digraphs can be recognized in polynomial-time remains unanswered. This is largely due to the lack of a good structural characterization for the class. In this paper, we study chronological rectangle digraphs which are also two-terminal series–parallel. We show that this restricted class of digraphs admits a forbidden induced subdigraph characterization, which leads to a polynomial-time recognition algorithm for this class of digraphs. [ABSTRACT FROM AUTHOR]

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]

Abstract An edge metric generator of a connected graph G is a vertex subset S for which every two distinct edges of G have distinct distance to some vertex of S , where the distance between a vertex v and an edge e is defined as the minimum of distances between v and the two endpoints of e in G. The smallest cardinality of an edge metric generator of G is the edge metric dimension, denoted by dim e (G). It follows that 1 ≤ dim e (G) ≤ n − 1 for any n -vertex graph G. A graph whose edge metric dimension achieves the upper bound is topful. In this paper, the structure of topful graphs is characterized, and many necessary and sufficient conditions for a graph to be topful are obtained. Using these results we design an O (n 3) time algorithm which determines whether a graph of order n is topful or not. Moreover, we describe and address an interesting class of topful graphs whose super graphs obtained by adding one edge are not topful. [ABSTRACT FROM AUTHOR]

Abstract This paper presents the theoretical properties of an algorithm to find a realization of a (full) n × n Euclidean distance matrix in the smallest possible embedding dimension. Our algorithm performs linearly in n , and quadratically in the minimum embedding dimension, which is an improvement w.r.t. other algorithms. [ABSTRACT FROM AUTHOR]

Abstract A planar graph can be drawn without edge crossings in the plane. It is well known that testing planarity of a graph can be solved in linear time. A graph is 1-planar, if it admits a 1-planar embedding, where each edge has at most one crossing. Testing 1-planarity of a graph is known to be NP-complete. This paper initiates the problem of testing 2-planarity of a graph, in particular, testing "full-outer-2-planarity" of a graph. A graph is outer- k -planar for an integer k ≥ 0 , if it admits an outer- k -planar embedding , that is, every vertex is on the outer boundary and no edge has more than k crossings. A graph is full-outer- k -planar , if it admits a full-outer- k -planar embedding , that is, an outer- k -planar embedding such that no crossing appears along the outer boundary. We present several structural properties of triconnected outer-2-planar graphs and full-outer-2-planar graphs, and prove that every triconnected full-outer-2-planar graph has a constant number of full-outer-2-planar embeddings. Based on these properties, we present linear-time algorithms for testing full-outer-2-planarity of a graph G , where G is connected, biconnected or triconnected. The algorithm also produces a full-outer-2-planar embedding of a graph, if it exists. Moreover, we show that every outer- k -planar embedding admits a straight-line drawing. [ABSTRACT FROM AUTHOR]

Abstract The units forms are algebraic expressions that have important role in representation theory of algebras. We identified that existing algorithms have exponential time complexity for weakly nonnegative and weakly positive types. In this paper we introduce a polynomial algorithm for the recognition of weakly nonnegative unit forms. The related algorithm identifies hypercritical restrictions in a given unit form, testing every subgraph of 9 vertices of the unit form associated graph. By adding Depth First Search approach, a similar strategy could be used in the recognition of weakly positive unit forms. We also present the most popular methods to decide whether or not a unit form is weakly nonnegative or weakly positive, we analyze their time complexity and we compare the results with our algorithms. [ABSTRACT FROM AUTHOR]

Abstract A set D ⊆ V of a graph G = (V , E) is called a dominating set of G if every vertex in V ∖ D has at least one neighbor in D. A dominating set D of G is a paired-dominating set of G if G [ D ] , the subgraph of G induced by D , has a perfect matching. Given a graph G , Min-Paired-Dom-Set is the problem to find a paired-dominating set of G of minimum cardinality. Min-Paired-Dom-Set is known to be NP -hard for general graphs and many other restricted classes of graphs. However, Min-Paired-Dom-Set is solvable in polynomial time in some graph classes including strongly chordal graphs and chordal bipartite graphs. In this paper, we strengthen this result by proposing a polynomial time algorithm to compute a minimum paired-dominating set in the class of strongly orderable graphs, which includes strongly chordal graphs and chordal bipartite graphs. The algorithm runs in linear time if a quasi-simple elimination ordering of the strongly orderable graph is provided. [ABSTRACT FROM AUTHOR]

Abstract: Fault-tolerant broadcasting and secure message distribution are important issues for network applications. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and security. An -dimensional folded hypercube, denoted by , is a strengthening variation of hypercube by adding additional links between nodes that have the furthest Hamming distance. In, , Ho(1990) proposed an algorithm for constructing edge-disjoint spanning trees each with a height twice the diameter of . Yang et al. (2009), recently proved that Ho’s spanning trees are indeed independent, i.e., any two spanning trees have the same root, say , and for any other node , the two different paths from to , one path in each tree, are internally node-disjoint. In this paper, we provide another construction scheme to produce independent spanning trees of , where the height of each tree is equal to the diameter of plus one. As a result, the heights of independent spanning trees constructed in this paper are shown to be optimal. [Copyright &y& Elsevier]

Abstract Several graph theoretic watermark methods have been proposed to encode numbers as graph structures in software watermarking environments. In this paper we propose an efficient and easily implementable codec system for encoding watermark numbers as reducible permutation flow-graphs and, thus, we extend the class of graphs used in such a watermarking environment. More precisely, we present an algorithm for encoding a watermark number w as a self-inverting permutation π ∗ , an algorithm for encoding the self-inverting permutation π ∗ into a reducible permutation graph F [ π ∗ ] whose structure resembles the structure of real program graphs, as well as decoding algorithms which extract the permutation π ∗ from the reducible permutation graph F [ π ∗ ] and the number w from π ∗. Both the encoding and the decoding process take, in the worst-case, time and space linear in the length of the binary representation of w. The two main components of our proposed codec system, i.e., the self-inverting permutation π ∗ and the reducible permutation graph F [ π ∗ ] , incorporate the binary representation of the watermark w in their structure and possess important structural properties, which make our system resilient to attacks; to this end, we experimentally evaluated our system under edge modification attacks on the graph F [ π ∗ ] and the results suggest that we can detect such attacks with high probability. [ABSTRACT FROM AUTHOR]

Abstract A graph of treewidth k has a representation by subtrees of a ternary tree, with subtrees of adjacent vertices sharing a tree node, and any tree node sharing at most k + 1 subtrees. Likewise for branchwidth, but with a shift to the edges of the tree rather than the nodes. In this paper we show that the mm-width of a graph – maximum matching width – combines aspects of both these representations, targeting tree nodes for adjacency and tree edges for the parameter value. The proof of this new characterization of mm-width is based on a definition of canonical minimum vertex covers of bipartite graphs. We show that these behave in a monotone way along branch decompositions over the vertex set of a graph. We use these representations to compare mm-width with treewidth and branchwidth, and also to give another new characterization of mm-width, by subgraphs of chordal graphs. We prove that given a graph G and a branch decomposition of maximum matching width k we can solve the Minimum Dominating Set Problem in time O ∗ (8 k) , thereby beating O ∗ (3 tw (G) ) whenever tw (G) > log 3 8 × k ≈ 1. 893 k. Note that mmw (G) ≤ tw (G) + 1 ≤ 3 mmw (G) and these inequalities are tight. Given only the graph G and using the best known algorithms to find decompositions, maximum matching width will be better for Minimum Dominating Set whenever tw (G) > 1. 549 × mmw (G). [ABSTRACT FROM AUTHOR]

Abstract Circle graphs are intersection graphs of chords in a circle and k -polygon graphs are intersection graphs of chords in a convex k -sided polygon where each chord has its endpoints on distinct sides. The k -polygon graphs, for k ≥ 2 , form an infinite chain of graph classes, each of which contains the class of permutation graphs. The union of all of those graph classes is the class of circle graphs. The polygon number ψ (G) of a circle graph G is the minimum k such that G is a k -polygon graph. Given a circle graph G and an integer k , determining whether ψ (G) ≤ k is NP-complete, while the problem is solvable in polynomial time for fixed k. In this paper, we show that ψ (G) is always at least as large as the asteroidal number of G , and equal to the asteroidal number of G when G is a connected distance hereditary graph that is not a clique. This implies that the classes of distance hereditary permutation graphs and distance hereditary AT-free graphs are the same, and we give a forbidden subgraph characterization of that class. We also establish the following upper bounds: ψ (G) is at most the clique cover number of G if G is not a clique, at most 1 plus the independence number of G , and at most ⌈ n ∕ 2 ⌉ where n ≥ 3 is the number of vertices of G. Our results lead to linear time algorithms for finding the minimum number of corners that must be added to a given circle representation to produce a polygon representation, and for finding the asteroidal number of a distance hereditary graph, both of which are improvements over previous algorithms for those problems. [ABSTRACT FROM AUTHOR]