Search

In the companion paper (Adler et al., 2017), we presented a characterization of the linear rank-width of distance-hereditary graphs, from which we derived an algorithm to compute it in polynomial time. In this paper, we investigate structural properties of distance-hereditary graphs based on this characterization. First, we prove that for a fixed tree T , every distance-hereditary graph of sufficiently large linear rank-width contains a vertex-minor isomorphic to T . We extend this property to bigger graph classes, namely, classes of graphs whose prime induced subgraphs have bounded linear rank-width. Here, prime graphs are graphs containing no splits. We conjecture that for every tree T , every graph of sufficiently large linear rank-width contains a vertex-minor isomorphic to T . Our result implies that it is sufficient to prove this conjecture for prime graphs. For a class Φ of graphs closed under taking vertex-minors, a graph G is called a vertex-minor obstruction for Φ if G ∉ Φ but all of its proper vertex-minors are contained in Φ . Secondly, we provide, for each k ⩾ 2 , a set of distance-hereditary graphs that contains all distance-hereditary vertex-minor obstructions for graphs of linear rank-width at most k . Also, we give a simpler way to obtain the known vertex-minor obstructions for graphs of linear rank-width at most 1. [ABSTRACT FROM AUTHOR]

Methods of finding sequence similarity play a significant role in computational biology. Owing to the rapid increase of genome sequences in public databases, the evolutionary relationship of species becomes more challenging. But traditional alignment-based methods are found inappropriate due to their time-consuming nature. Therefore, it is necessary to find a faster method, which applies to species phylogeny. In this paper, a new graph-theory based alignment-free sequence comparison method is proposed. A complete-bipartite graph is used to represent each genome sequence based on its nucleotide triplets. Subsequently, with the help of the weights of edges of the graph, a vector descriptor is formed. Finally, the phylogenetic tree is drawn using the UPGMA algorithm. In the present case, the datasets for comparison are related to mammals, viruses, and bacteria. In most of the cases, the phylogeny in the present case is found to be more satisfactory as compared to earlier methods. • A new graph-theory based alignment-free genome sequence comparison. • Use of complete bipartite graph to represent genome sequences. • Descriptor based on the weights of the edges of the graph. • Comparison of the phylogenetic trees of different mammals, viruses, and bacteria. • Less time complexity compared to that of earlier methods. [ABSTRACT FROM AUTHOR]

This paper deals with two types of repetitions in strings: squares , which consist of two adjacent occurrences of substrings, and runs , which are periodic substrings that cannot be extended further to the left or right while maintaining the period. We show how to compute all the primitively-rooted squares in a given partial word, which is a sequence that may have undefined positions, called holes or wildcards, that match any letter of the alphabet over which the sequence is defined. We also describe an algorithm for computing all primitively-rooted runs in a given partial word and extend previous analyses on the number of runs to partial words. [ABSTRACT FROM AUTHOR]

A perfect 2-matching in an undirected graph G = ( V , E ) is a function x : E → 0 , 1 , 2 such that for each node v ∈ V the sum of values x ( e ) on all edges e incident to v equals 2. If supp ( x ) = e ∈ E ∣ x ( e ) ≠ 0 contains no triangles then x is called triangle-free . Polyhedrally speaking, triangle-free 2-matchings are harder than 2-matchings, but easier than usual 1-matchings. Given edge costs c : E → R + , a natural combinatorial problem consists in finding a perfect triangle-free matching of minimum total cost. For this problem, Cornuéjols and Pulleyblank devised a combinatorial strongly-polynomial algorithm, which can be implemented to run in O ( V E log V ) time. (Here we write V , E to indicate their cardinalities | V | , | E | .) If edge costs are integers in range [ 0 , C ] then for both 1- and 2-matchings some faster scaling algorithms are known that find optimal solutions within O ( V α ( E , V ) log V E log ( V C ) ) and O ( V E log ( V C ) ) time, respectively, where α denotes the inverse Ackermann function. So far, no efficient cost-scaling algorithm is known for finding a minimum-cost perfect triangle-free2-matching. The present paper fills this gap by presenting such an algorithm with time complexity of O ( V E log V log ( V C ) ) . [ABSTRACT FROM AUTHOR]

One of the most famous algorithmic meta-theorems states that every graph property which can be defined in counting monadic second order logic (CMSOL) can be checked in linear time on graphs of bounded treewidth, which is known as Courcelle’s Theorem (Courcelle, 1990). These algorithms are constructed as finite state tree automata and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e. every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. In this paper we prove two special cases of this conjecture, first for the class of k -outerplanar graphs, which are known to have treewidth at most 3 k − 1 (Bodlaender, 1998) and for graphs of bounded treewidth without chordless cycles of length at least some constant ℓ . We furthermore show that for a proof of Courcelle’s Conjecture it is sufficient to show that all members of a graph class admit constant width tree decompositions whose bags and edges can be identified with MSOL-predicates. For graph classes that admit MSOL-definable constant width tree decompositions that have bounded degree or allow for a linear ordering of all nodes with the same parent we even give a stronger result: In that case, the counting predicates of CMSOL are not needed. [ABSTRACT FROM AUTHOR]

Many problems on graphs can be expressed in the following language: given a graph G = ( V , E ) and a terminal set T ⊆ V , find a minimum size set S ⊆ V which intersects all “structures” (such as cycles or paths) passing through the vertices in T . We refer to this class of problems as terminal set problems. In this paper, we introduce a general method to obtain faster exact exponential time algorithms for several terminal set problems. In the process, we break the O ⁎ ( 2 n ) barrier for the classic Node Multiway Cut , Directed Unrestricted Node Multiway Cut and Directed Subset Feedback Vertex Set problems. [ABSTRACT FROM AUTHOR]

Abstract: For many of the unsolved problems concerning cycles and matchings in graphs it is known that it is sufficient to prove them for snarks, the class of non-trivial 3-regular graphs which cannot be 3-edge coloured. In the first part of this paper we present a new algorithm for generating all non-isomorphic snarks of a given order. Our implementation of the new algorithm is 14 times faster than previous programs for generating snarks, and 29 times faster for generating weak snarks. Using this program we have generated all non-isomorphic snarks on vertices. Previously lists up to vertices have been published. In the second part of the paper we analyze the sets of generated snarks with respect to a number of properties and conjectures. We find that some of the strongest versions of the cycle double cover conjecture hold for all snarks of these orders, as does Jaegerʼs Petersen colouring conjecture, which in turn implies that Fulkersonʼs conjecture has no small counterexamples. In contrast to these positive results we also find counterexamples to eight previously published conjectures concerning cycle coverings and the general cycle structure of cubic graphs. [Copyright &y& Elsevier]

The Disjoint Paths Problem asks, given a graph G and a set of pairs of terminals ( s 1 , t 1 ) , … , ( s k , t k ) , whether there is a collection of k pairwise vertex-disjoint paths linking s i and t i , for i = 1 , … , k . In their f ( k ) ⋅ n 3 algorithm for this problem, Robertson and Seymour introduced the irrelevant vertex technique according to which in every instance of treewidth greater than g ( k ) there is an “irrelevant” vertex whose removal creates an equivalent instance of the problem. This fact is based on the celebrated Unique Linkage Theorem , whose – very technical – proof gives a function g ( k ) that is responsible for an immense parameter dependence in the running time of the algorithm. In this paper we give a new and self-contained proof of this result that strongly exploits the combinatorial properties of planar graphs and achieves g ( k ) = O ( k 3 / 2 ⋅ 2 k ) . Our bound is radically better than the bounds known for general graphs. [ABSTRACT FROM AUTHOR]

Abstract: The Feedback Vertex Set problem asks whether a graph contains vertices meeting all its cycles. This is not a local property, in the sense that we cannot check if vertices meet all cycles by looking only at their neighbors. Dynamic programming algorithms for problems based on non-local properties are usually more complicated. In this paper, given a graph of clique-width and a -expression of , we solve the Minimum Feedback Vertex Set problem in time . Our algorithm applies dynamic programming on a so-called -module decomposition of a graph, as defined by Rao (2008) [29], which is easily derivable from a-expression of the graph. The related notion of module-width of a graph is tightly linked to both clique-width and NLC-width, and in this paper we give an alternative equivalent characterization of module-width. [Copyright &y& Elsevier]

The average-case analysis of probabilistic algorithms has proved to be very successful for finding asymptotic bounds on parameters of random regular graphs. Recently, the authors obtained a general transfer result which translates such bounds into (deterministic) results about all regular graphs with sufficiently large girth. In this paper, we apply this methodology to obtain new upper or lower bounds on the size of maximum independent sets and power dominating sets in cubic graphs with large girth, and maximum cuts, maximum and minimum bisections, and minimum connected and weakly-connected dominating sets in r -regular graphs with large girth. All the new bounds improve upon the best previous bounds. For independent sets in cubic graphs, this also improves on the best “almost sure” bounds for random cubic graphs. [ABSTRACT FROM AUTHOR]

A graph H is immersed in a graph G if the vertices of H are mapped to (distinct) vertices of G , and the edges of H are mapped to paths joining the corresponding pairs of vertices of G , in such a way that the paths are pairwise edge-disjoint. The notion of an immersion is quite similar to the well-known notion of a minor, as structural approach inspired by the theory of graph minors has been extremely successful in immersions. Hadwiger's conjecture on graph coloring, generalizing the Four Color Theorem, states that every loopless graph without a K k -minor is ( k − 1 ) -colorable, where K k is the complete graph on k vertices. This is a long standing open problem in graph theory, and it is even unknown whether it is possible to determine ck -colorability of K k -minor-free graphs in polynomial time for some constant c . In this paper, we address coloring graphs without H -immersion. In contrast to coloring H -minor-free graphs, we show the following: 1. there exists a fixed-parameter algorithm to decide whether or not a given graph G without an immersion of a graph H of maximum degree d is ( d − 1 ) -colorable, where the size of H is a parameter. In fact, if G is ( d − 1 ) -colorable, the algorithm produces such a coloring, and 2. for any positive integer k ( k ≥ 6 ), it is NP-complete to decide whether or not a given graph G without a K k -immersion is ( k − 3 ) -colorable. [ABSTRACT FROM AUTHOR]

This paper presents improved algorithms for the round-trip single-facility location problem on a general graph, in which a set A of collection depots is given and the service distance of a customer is defined to be the distance from the server, to the customer, then to a depot, and back to the server. Each customer i is associated with a subset A i ⊆ A of depots that i can potentially select from and use. When A i = A for each customer i , the problem is unrestricted; otherwise it is restricted. For the restricted round-trip 1-center problem, we give an O ( m n lg ⁡ n ) -time algorithm. For the restricted 1-median problem, we give an O ( m n lg ⁡ ( | A | / m ) + n 2 lg ⁡ n ) -time algorithm. For the unrestricted 1-median problem, we give an O ( m n + n 2 lg ⁡ lg ⁡ n ) -time algorithm. [ABSTRACT FROM AUTHOR]

Abstract: Self-stabilizing algorithms for optimization problems can often be solved more easily using the distance-two model in which each vertex can instantly see the state information of all vertices up to distance two. This paper presents a new technique to emulate algorithms for the distance-two model on the distance-one model using the distributed scheduler with a slowdown factor of moves. Up until now the best transformer had a slowdown factor of moves. The technique is used to derive improved self-stabilizing algorithms for several graph domination problems. The paper also introduces a generalization of the distance-two model allowing a more space efficient transformer. [Copyright &y& Elsevier]

Abstract: This paper presents a pattern language based on regular expressions that allows the introduction of variables that can be instantiated to portions of the path that matches the expression. The paper will define a simple syntax for the language and its formal semantics. It will also study a modification of finite state automata that, through the introduction of actions on transitions, allows the variables to be instantiated while matching the expression. Finally, the paper will show that the problem of answering queries with variables is inherently harder than simple matching, essentially because, even for fairly simple expressions, the size of the results can be exponential in the size of the graph. The class of expressions and a class of graphs for which query answering is polynomial will be identified, and a processing algorithm for these expressions based on the intersection graph will be provided and analyzed. [Copyright &y& Elsevier]

Abstract: In this paper, we define and analyze the nowhere dense classes of graphs. This notion is a common generalization of proper minor closed classes, classes of graphs with bounded degree, locally planar graphs, classes with bounded expansion, to name just a few classes which are studied extensively in combinatorial and computer science contexts. In this paper, we show that this concept leads to a classification of general classes of graphs and to the dichotomy between nowhere dense and somewhere dense classes. This classification is surprisingly stable as it can be expressed in terms of the most commonly used basic combinatorial parameters, such as the independence number , the clique number , and the chromatic number . The remarkable stability of this notion and its robustness has a number of applications to mathematical logic, complexity of algorithms, and combinatorics. We also express the nowhere dense versus somewhere dense dichotomy in terms of edge densities as a trichotomy theorem. [Copyright &y& Elsevier]

Abstract: One major area of difficulty in developing an algorithm for embedding a graph on a surface is handling bridges which have more than one possible placement. This paper addresses a number of published algorithms where this has not been handled correctly. This problem arises in certain presentations of the Demoucron, Malgrange and Pertuiset planarity testing algorithm. It also occurs in an algorithm of Filotti for embedding 3-regular graphs on the torus. The same error appears in an algorithm for embedding graphs of arbitrary genus by Filotti, Miller and Reif. It is also present in an algorithm for embedding graphs of arbitrary genus by Djidjev and Reif. The omission regarding the Demoucron, Malgrange and Pertuiset planarity testing algorithm is easily remedied. However there appears to be no way of correcting the algorithms of the other papers without making the algorithms take exponential time. [ABSTRACT FROM AUTHOR]

Abstract: This paper is composed of two parts. In the first part, an improved algorithm is presented for the problem of finding length-bounded two vertex-disjoint paths in an undirected planar graph. The presented algorithm requires time and space, where is the smaller of the two given length bounds. In the second part of this paper, we consider the minmax k vertex-disjoint paths problem on a directed acyclic graph, where is a constant. An improved algorithm and a faster approximation scheme are presented. The presented algorithm requires time and space, and the presented approximation scheme requires time and space, where ϵ is the given approximation parameter and M is the length of the longest path in an optimal solution. [ABSTRACT FROM AUTHOR]

Abstract: Effective task scheduling is essential for obtaining high performance in heterogeneous computing systems (HCS). However, finding an effective task schedule in HCS, requires the consideration of the heterogeneity of computation and communication. To solve this problem, we present a list scheduling algorithm, called Heterogeneous Earliest Finish with Duplicator (HEFD). As task priority is a key attribute for list scheduling algorithm, this paper presents a new approach for computing their priority which considers the performance difference in target HCS using variance. Another novel idea proposed in this paper is to try to duplicate all parent tasks and get an optimal scheduling solution. The comparison study, based on both randomly generated graphs and the graphs of some real applications, shows that our scheduling algorithm HEFD significantly surpasses other three well-known algorithms. [Copyright &y& Elsevier]

Abstract: The main results of this paper are based on the idea that most load balancing algorithms can be described in the framework of optimization theory. It enables to involve classical results linked with convergence, its speed and other elements. We emphasize that these classical results have been found independently and till now this connection has not been shown clearly. In this paper, we analyze the load balancing algorithm based on the steepest descent algorithm. The analysis shows that the speed of convergence is determined by eigenvalues of the Laplacian for the graph of a given load balancing system. This consideration also leads to the problems of choosing an optimal structure for a load balancing system. We prove that these optimal graphs have special Laplacians: the multiplicities of their minimal and maximal positive eigenvalues must be greater than one. Such a property is essential for strongly regular graphs, investigated in algebraic graph theory. [Copyright &y& Elsevier]

Abstract: Recent work of Gowers [T. Gowers, A new proof of Szemerédi''s theorem, Geom. Funct. Anal. 11 (2001) 465–588] and Nagle, Rödl, Schacht, and Skokan [B. Nagle, V. Rödl, M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Regularity lemma for k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Applications of the regularity lemma for uniform hypergraphs, preprint] has established a hypergraph removal lemma, which in turn implies some results of Szemerédi [E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975) 299–345], and Furstenberg and Katznelson [H. Furstenberg, Y. Katznelson, An ergodic Szemerédi theorem for commuting transformations, J. Anal. Math. 34 (1978) 275–291] concerning one-dimensional and multidimensional arithmetic progressions, respectively. In this paper we shall give a self-contained proof of this hypergraph removal lemma. In fact we prove a slight strengthening of the result, which we will use in a subsequent paper [T. Tao, The Gaussian primes contain arbitrarily shaped constellations, preprint] to establish (among other things) infinitely many constellations of a prescribed shape in the Gaussian primes. [Copyright &y& Elsevier]

Abstract: This paper presents parallel algorithms for recognizing chordal_planar graphs and planar -trees. Both the algorithms run in time using processors on a concurrent-read and concurrent-write (CRCW), parallel random access machine (PRAM) model, where n and m are, respectively, the number of nodes and edges in the graph.The novelty of our chordal_planar graph recognition algorithm lies in that it is based on an elegant structural characterization of chordal_planar graphs proposed in this paper. Moreover, it is simpler than separately testing chordality and planarity. Our planar k-trees recognition algorithm is based on a new characterization of k-trees presented in this paper. [Copyright &y& Elsevier]

Abstract: Gossiping is an extensively investigated information dissemination process in which each processor has a distinct item of information and has to collect all the items possessed by the other processors. In this paper we provide an innovative and general lower bound technique relying on the novel notion of delay digraph of a gossiping protocol and on the use of matrix norm methods. Such a technique is very powerful and allows the determination of new and significantly improved lower bounds in many cases. In fact, we derive the first general lower bound on the gossiping time of systolic protocols, i.e., constituted by a periodic repetition of simple communication steps. In particular, given any network of n processors and any systolic period s, in the directed and the undirected half-duplex cases every s-systolic gossip protocol takes at least log(n)/log(1/λ)−O(loglog(n)) time steps, where λ is the unique solution between 0 and 1 of , with p i (λ)=1+ λ 2 +⋯+ λ 2i −2 for any integer i >0. We then provide improved lower bounds in the directed and half-duplex cases for many well-known network topologies, such as Butterfly, de Bruijn, and Kautz graphs. All the results are extended also to the full-duplex case. Our technique is very general, as for s →∞ it allows the determination of improved results even for non-systolic protocols. In fact, for general networks, as a simple corollary it yields a lower bound only an O(loglog(n)) additive factor far from the general one independently proved in [Proc. 1st ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1989, p. 318; Topics in Combinatorics and Graph Theory (1990) 451; SIAM Journal on Computing 21(1) (1992) 111; Discrete Applied Mathematics 42 (1993) 75] for all graphs and any (non-systolic) gossip protocol. Moreover, for specific networks, it significantly improves with respect to the previously known results, even in the full-duplex case. Correspondingly, better lower bounds on the gossiping time of non-systolic protocols are determined in the directed, half-duplex and full-duplex cases for Butterfly, de Bruijn, and Kautz graphs. Even if in this paper we give only a limited number of examples, our technique has wide applicability and gives a general framework that often allows to get improved lower bounds on the gossiping time of systolic and non-systolic protocols in the directed, half-duplex and full-duplex cases. [Copyright &y& Elsevier]

We study the problem of determining whether an n -node graph G contains an even hole , i.e., an induced simple cycle consisting of an even number of nodes. Conforti, Cornuéjols, Kapoor, and Vušković gave the first polynomial-time algorithm for the problem, which runs in O ( n 40 ) time. Later, Chudnovsky, Kawarabayashi, and Seymour reduced the running time to O ( n 31 ) . The best previously known algorithm for the problem, due to da Silva and Vušković, runs in O ( n 19 ) time. In this paper, we solve the problem in O ( n 11 ) time via a decomposition-based algorithm that relies on the decomposition theorem of da Silva and Vušković. Moreover, if G contains even holes, then our algorithm also outputs an even hole of G in O ( n 11 ) time. [ABSTRACT FROM AUTHOR]

The main problem in information storage has previously been how large amounts of data can be stored. However, the technological development over the years has been able to give rather satisfactory answers to this problem. Recently, the focus has shifted towards determining how stored information can be efficiently retrieved. This problem is addressed in an article by E. Yaakobi and J. Bruck (2012), where information retrieval in associative memories is studied. In this paper, we focus on the case where the retrieved information unit is unambiguous. In particular, we present characterizations and study various extremal properties of such associative memories. Moreover, the algorithmic complexity of certain naturally rising problems is considered. [ABSTRACT FROM AUTHOR]

Abstract: Minimum Fill-in is a fundamental and classical problem arising in sparse matrix computations. In terms of graphs it can be formulated as a problem of finding a triangulation of a given graph with the minimum number of edges. In this paper, we study the parameterized complexity of local search for the Minimum Fill-in problem in the following form: Given a triangulation H of a graph G, is there a better triangulation, i.e. triangulation with less edges than H, within a given distance from H? We prove that this problem is fixed-parameter tractable (FPT) being parameterized by the distance from the initial triangulation, by providing an algorithm that in time decides if a better triangulation of G can be obtained by swapping at most k edges of H. Our result adds Minimum Fill-in to the list of very few problems for which local search is known to be FPT. [Copyright &y& Elsevier]

Abstract: The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a firefighter may be placed on an unburned vertex, permanently protecting it, and the fire spreads to all neighboring unprotected vertices of burning vertices. The goal is to let as few vertices burn as possible. In this paper, we consider a generalization of this problem, where at each time step firefighters can be deployed. Our results answer several open questions raised by Cai et al. [8]. We show that this problem is W[1]-hard when parameterized by the number of saved vertices, protected vertices, and burned vertices. We also investigate several combined parameterizations for which the problem is fixed-parameter tractable. Some of our algorithms improve on previously known algorithms. We also establish lower bounds to polynomial kernelization. [Copyright &y& Elsevier]

Abstract: A bisection of a graph G is a bipartition , of such that . It is NP-hard to find a bisection , of a graph G maximizing (respectively, minimizing ), where denotes the number of edges of G between and , and denotes the number of edges of G with both ends in . There has been algorithmic work on bisections, but very few extremal results are known. Bollobás and Scott conjectured that if G is a graph with m edges and minimum degree at least 2 then G admits a bisection such that . In this paper, we confirm this conjecture and show that the triangle is the only extremal graph. Moreover, the bound cannot be improved to , for any , by excluding or by increasing the minimum degree from 2 to 3. [Copyright &y& Elsevier]

Abstract: In this paper, we present a design methodology that uses a combined graphical and scheduling technique to map C-based high level language (HLL) based applications to FPGA. Although there are a number of approaches addressing the mapping from HLL to hardware, many of these existing solutions either require a steep learning curve or do not produce an appropriate mapping pattern for the hardware platform. We provide a solution to this problem, by analyzing the data flow and data dependencies in the given code and proposing a scheduling patterns for the given algorithm. We then provide a suitable mapping pattern for the hardware platform. We use the mapping pattern to deliver synthesizable HDL (Verilog) code. We demonstrate our design methodology with results from different real-time case studies that are based on different algorithms. [Copyright &y& Elsevier]

Abstract: A linear coloring of a graph is a proper coloring of the vertices of the graph so that each pair of color classes induces a union of disjoint paths. In this paper, we prove that for every connected graph with maximum degree at most three and every assignment of lists of size four to the vertices of the graph, there exists a linear coloring such that the color of each vertex belongs to the list assigned to that vertex and the neighbors of every degree-two vertex receive different colors, unless the graph is or . This confirms a conjecture raised by Esperet, Montassier and Raspaud [L. Esperet, M. Montassier, and A. Raspaud, Linear choosability of graphs, Discrete Math. 308 (2008) 3938–3950]. Our proof is constructive and yields a linear-time algorithm to find such a coloring. [Copyright &y& Elsevier]

Abstract: In this paper we develop new algorithmic machinery for solving hard problems on graphs of bounded rank-width and on digraphs of bounded bi-rank-width in polynomial (XP, to be precise) time. These include, particularly, graph coloring and chromatic polynomial problems, the Hamiltonian path and -min-leaf outbranching, the directed cut, and more generally MSOL-partitioning problems on digraphs. Our focus on a formally clean and unified approach for the considered algorithmic problems is in contrast with many previous published XP algorithms running on graphs of bounded clique-width, which mostly used ad hoc techniques and ideas. The new contributions include faster algorithms for computing the chromatic number and the chromatic polynomial on graphs of bounded rank-width, and new algorithms for solving the defective coloring, the min-leaf outbranching, and the directed cut problems. [Copyright &y& Elsevier]

Abstract: In this paper we prove that the problem of deciding whether a given -uniform hypergraph , with minimum -wise vertex degree at least , contains a matching missing exactly vertices, that is, a set of disjoint edges of size , is NP-complete for , while for and we provide a polynomial time algorithm for the corresponding search problem. For the perfect case, , we show that the problem is NP-complete for and give a polynomial time algorithm for leaving a hardness gap in . Our reduction carries over to the more general case when, for , the minimum -wise codegree of a -uniform hypergraph is considered. In particular, for and we deduce that the problem of deciding the existence of a perfect matching in a given -uniform hypergraph , with minimum degree at least , is NP-complete for , complementing a fact proved recently in Han et al. (2009) [8] that the problem is trivial for . In addition, we use our reduction to show that a problem of deciding the existence of a perfect packing of the cycle into a 3-uniform hypergraph with minimum -wise vertex degree at least is NP-complete only for , which combined with a result from Kühn and Osthus (2006) [16] is, again, asymptotically tight. [Copyright &y& Elsevier]

Abstract: A vertex subset  of a graph  is a dominating set if every vertex of is either in or is adjacent to a vertex in . The paired domination problem on asks for a minimum-cardinality dominating set  of such that the subgraph induced by contains a perfect matching; motivation for this problem comes from the interest in finding a small number of locations to place pairs of mutually visible guards so that the entire set of guards monitors a given area. The paired domination problem on general graphs is known to be NP-complete. In this paper, we consider the paired domination problem on permutation graphs. We define an embedding of permutation graphs in the plane which enables us to obtain an equivalent version of the problem involving points in the plane, and we describe a sweeping algorithm for this problem; if the permutation over the set  defining a permutation graph  on vertices is given, our algorithm computes a paired dominating set of in time, and is therefore optimal. [Copyright &y& Elsevier]

Abstract: In this paper we consider the class of simple graphs defined by excluding, as induced subgraphs, even holes (i.e. chordless cycles of even length). These graphs are known as even-hole-free graphs. We prove a decomposition theorem for even-hole-free graphs, that uses star cutsets and 2-joins. This is a significant strengthening of the only other previously known decomposition of even-hole-free graphs, by Conforti, Cornuéjols, Kapoor and Vušković, that uses 2-joins and star, double star and triple star cutsets. It is also analogous to the decomposition of Berge (i.e. perfect) graphs with skew cutsets, 2-joins and their complements, by Chudnovsky, Robertson, Seymour and Thomas. The similarity between even-hole-free graphs and Berge graphs is higher than the similarity between even-hole-free graphs and simply odd-hole-free graphs, since excluding a 4-hole, automatically excludes all antiholes of length at least 6. In a graph that does not contain a 4-hole, a skew cutset reduces to a star cutset, and a 2-join in the complement implies a star cutset, so in a way it was expected that even-hole-free graphs can be decomposed with just the star cutsets and 2-joins. A consequence of this decomposition theorem is a recognition algorithm for even-hole-free graphs that is significantly faster than the previously known ones. [Copyright &y& Elsevier]

Abstract: Let G be a finite connected simple graph with d vertices and let be the edge polytope of G. We call decomposable if decomposes into integral polytopes and via a hyperplane. In this paper, we explore various aspects of decomposition of : we give an algorithm deciding the decomposability of , we prove that is normal if and only if both and are normal, and we also study how a condition on the toric ideal of (namely, the ideal being generated by quadratic binomials) behaves under decomposition. [Copyright &y& Elsevier]

Abstract: In the graph searching game the opponents are a set of searchers and a fugitive in a graph. The searchers try to capture the fugitive by applying some sequence of moves that include placement, removal, or sliding of a searcher along an edge. The fugitive tries to avoid capture by moving along unguarded paths. The search number of a graph is the minimum number of searchers required to guarantee the capture of the fugitive. In this paper, we initiate the study of this game under the natural restriction of connectivity where we demand that in each step of the search the locations of the graph that are clean (i.e. non-accessible to the fugitive) remain connected. We give evidence that many of the standard mathematical tools used so far in classic graph searching fail under the connectivity requirement. We also settle the question on “the price of connectivity”, that is, how many searchers more are required for searching a graph when the connectivity demand is imposed. We make estimations of the price of connectivity on general graphs and we provide tight bounds for the case of trees. In particular, for an n-vertex graph the ratio between the connected searching number and the non-connected one is while for trees this ratio is always at most 2. We also conjecture that this constant-ratio upper bound for trees holds also for all graphs. Our combinatorial results imply a complete characterization of connected graph searching on trees. It is based on a forbidden-graph characterization of the connected search number. We prove that the connected search game is monotone for trees, i.e. restricting search strategies to only those where the clean territories increase monotonically does not require more searchers. A consequence of our results is that the connected search number can be computed in polynomial time on trees, moreover, we show how to make this algorithm distributed. Finally, we reveal connections of this parameter to other invariants on trees such as the Horton–Strahler number. [Copyright &y& Elsevier]

Abstract: In Howlett and Nguyen (2010) , the concept of a W-graph ideal in a Coxeter group was introduced, and it was shown how a W-graph can be constructed from a given W-graph ideal. In this paper, we describe a class of W-graph ideals from which certain Kazhdan–Lusztig left cells arise. The result justifies the algorithm as illustrated in Howlett and Nguyen (2010) for the construction of W-graphs for Specht modules for the Hecke algebra of type A. [Copyright &y& Elsevier]

Abstract: We introduce a concept of a W-graph ideal in a Coxeter group. The main goal of this paper is to describe how to construct a W-graph from a given W-graph ideal. The principal application of this idea is in type A, where it provides an algorithm for the construction of W-graphs for Specht modules. [Copyright &y& Elsevier]

Abstract: We consider the problem of making a given -connected graph k-connected by adding a minimum number of new edges, which we call the k-connectivity augmentation problem. In this paper, we deal with the problem when where n is the number of vertices of the input graph. By considering the complement graph, the -connectivity augmentation problem can be reduced to the problem of finding a maximum square-free 2-matching in a simple graph with maximum degree at most three. We give a polynomial-time algorithm to find a maximum square-free 2-matching in a simple graph with maximum degree at most three, which yields a polynomial-time algorithm for the -connectivity augmentation problem. Our algorithm is based on the fact that the square-free 2-matchings are endowed with a matroid structure called a jump system. We also show that the weighted -connectivity augmentation problem can be solved in polynomial time if the weights are induced by a function on the vertex set, whereas the problem is NP-hard for general weights. [Copyright &y& Elsevier]

Abstract: Classes with bounded expansion, which generalise classes that exclude a topological minor, have recently been introduced by Nešetřil and Ossona de Mendez. These classes are defined by the fact that the maximum average degree of a shallow minor of a graph in the class is bounded by a function of the depth of the shallow minor. Several linear-time algorithms are known for bounded expansion classes (such as subgraph isomorphism testing), and they allow restricted homomorphism dualities, amongst other desirable properties. In this paper, we establish two new characterisations of bounded expansion classes, one in terms of so-called topological parameters and the other in terms of controlling dense parts. The latter characterisation is then used to show that the notion of bounded expansion is compatible with the Erdös–Rényi model of random graphs with constant average degree. In particular, we prove that for every fixed , there exists a class with bounded expansion, such that a random graph of order and edge probability asymptotically almost surely belongs to the class. We then present several new examples of classes with bounded expansion that do not exclude some topological minor, and appear naturally in the context of graph drawing or graph colouring. In particular, we prove that the following classes have bounded expansion: graphs that can be drawn in the plane with a bounded number of crossings per edge, graphs with bounded stack number, graphs with bounded queue number, and graphs with bounded non-repetitive chromatic number. We also prove that graphs with ‘linear’ crossing number are contained in a topologically-closed class, while graphs with bounded crossing number are contained in a minor-closed class. [Copyright &y& Elsevier]

Abstract: A (loopless) digraph H is strongly immersed in a digraph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths used are pairwise edge-disjoint, and do not pass through vertices of G that are images of vertices of H. A digraph has cutwidth at most k if its vertices can be ordered in such a way that for each j, there are at most k edges uv such that and . We prove that for every set of tournaments, the following are equivalent: [•] there is a digraph H such that H cannot be strongly immersed in any member of , [•] there exists k such that every member of has cutwidth at most k, [•] there exists k such that every vertex of every member of belongs to at most k edge-disjoint directed cycles. This is a key lemma towards two results that will be presented in later papers: first, that strong immersion is a well-quasi-order for tournaments, and second, that there is a polynomial time algorithm for the k edge-disjoint directed paths problem (for fixed k) in a tournament. [Copyright &y& Elsevier]

Abstract: This paper shows that the FPTAS for the min–max disjoint paths problem on directed acyclic graphs by Yu et al. (2010) can be improved by a rounding and searching technique. [Copyright &y& Elsevier]

Abstract: In recent years, the issue of energy consumption in parallel and distributed computing systems has attracted a great deal of attention. In response to this, many energy-aware scheduling algorithms have been developed primarily using the dynamic voltage–frequency scaling (DVFS) capability which has been incorporated into recent commodity processors. Majority of these algorithms involve two passes: schedule generation and slack reclamation. The former pass involves the redistribution of tasks among DVFS-enabled processors based on a given cost function that includes makespan and energy consumption, while the latter pass is typically achieved by executing individual tasks with slacks at a lower processor frequency. In this paper, a new slack reclamation algorithm is proposed by approaching the energy reduction problem from a different angle. Firstly, the problem of task slack reclamation by using combinations of processors’ frequencies is formulated. Secondly, several proofs are provided to show that (1) if the working frequency set of processor is assumed to be continues, the optimal energy will be always achieved by using only one frequency, (2) for real processors with a discrete set of working frequencies, the optimal energy is always achieved by using at most two frequencies, and (3) these two frequencies are adjacent/neighbouring when processor energy consumption is a convex function of frequency. Thirdly, a novel algorithm to find the best combination of frequencies to result the optimal energy is presented. The presented algorithm has been evaluated based on results obtained from experiments with three different sets of task graphs: 3000 randomly generated task graphs, and 600 task graphs for two popular applications (Gauss–Jordan and LU decomposition). The results show the superiority of the proposed algorithm in comparison with other techniques. [Copyright &y& Elsevier]

Abstract: A metric graph is a geometric realization of a finite graph by identifying each edge with a real interval. A divisor on a metric graph Γ is an element of the free abelian group on Γ. The rank of a divisor on a metric graph is a concept appearing in the Riemann–Roch theorem for metric graphs (or tropical curves) due to Gathmann and Kerber, and Mikhalkin and Zharkov. We define a rank-determining set of a metric graph Γ to be a subset A of Γ such that the rank of a divisor D on Γ is always equal to the rank of D restricted on A. We show constructively in this paper that there exist finite rank-determining sets. In addition, we investigate the properties of rank-determining sets in general and formulate a criterion for rank-determining sets. Our analysis is based on an algorithm to derive the -reduced divisor from any effective divisor in the same linear system. [Copyright &y& Elsevier]

Abstract: We take a graph theoretic approach to the problem of finding generators for those prime ideals of which are invariant under the torus action . Launois (2004) has shown that the generators consist of certain quantum minors of the matrix of canonical generators of and in Launois (2004) gives an algorithm to find them. In this paper we modify a classic result of Lindström (1973) and Gessel and Viennot (1985) to show that a quantum minor is in the generating set for a particular ideal if and only if we can find a particular set of vertex-disjoint directed paths in an associated directed graph. [Copyright &y& Elsevier]

Abstract: Many scientific applications can be structured as parallel task graphs (PTGs), that is, graphs of data-parallel tasks. Adding data parallelism to a task-parallel application provides opportunities for higher performance and scalability, but poses additional scheduling challenges. In this paper, we study the off-line scheduling of multiple PTGs on a single, homogeneous cluster. The objective is to optimize performance without compromising fairness among the PTGs. We consider the range of previously proposed scheduling algorithms applicable to this problem, from both the applied and the theoretical literature, and we propose minor improvements when possible. Our main contribution is an extensive evaluation of these algorithms in simulation, using both synthetic and real-world application configurations, using two different metrics for performance and one metric for fairness. We identify a handful of algorithms that provide good trade-offs when considering all these metrics. The best algorithm overall is one that structures the schedule as a sequence of phases of increasing duration based on a makespan guarantee produced by an approximation algorithm. [Copyright &y& Elsevier]

Abstract: This paper presents a hash and a canonicalization algorithm for Notation 3 (N3) and Resource Description Framework (RDF) graphs. The hash algorithm produces, given a graph, a hash value such that the same value would be obtained from any other equivalent graph. Contrary to previous related work, it is well-suited for graphs with blank nodes, variables and subgraphs. The canonicalization algorithm outputs a canonical serialization of a given graph (i.e. a canonical representative of the set of all the graphs that are equivalent to it). Potential applications of these algorithms include, among others, checking graphs for identity, computing differences between graphs and graph synchronization. The former could be especially useful for crawlers that gather RDF/N3 data from the Web, to avoid processing several times graphs that are equivalent. Both algorithms have been evaluated on a big dataset, with more than 29 million triples and several millions of subgraphs and variables. [Copyright &y& Elsevier]

Abstract: Let be a graph and let and be two integer-valued functions defined on such that for every . Let be vertex-disjoint subgraphs of with (). In this paper, we prove that every -graph contains a subgraph such that has a -factorization orthogonal to (), where and are positive integers with . We also prove that there are polynomial-time algorithms for finding the desired subgraph . [ABSTRACT FROM AUTHOR]

Abstract: The utilization of the limited resources of a multiprocessor or multicomputer system is a primary performance issue which is crucial for the design of many scheduling algorithms. While many of the existing parallel machines benefit from a regular product network topology, almost none of the previous resource placement techniques have come to recognize and exploit this inherent regularity. This paper introduces several novel algorithms for deriving resource placement schemes in product networks based on the assumption of perfect resource placement in their underling basic graphs. Our techniques use known schemes for the basic networks as their building blocks for deploying the resource placement scheme in the product network. This seriously cuts down the expenses required for deploying and rescaling the network. In particular, we propose some efficient algorithms for adjacency placement in a product of heterogeneous graphs. Furthermore, we extend our approach and present algorithms for distant resource placement in product networks. [Copyright &y& Elsevier]

Abstract: We introduce the idea of Assur graphs, a concept originally developed and exclusively employed in the literature of the kinematics community. This paper translates the terminology, questions, methods and conjectures from the kinematics terminology for one degree of freedom linkages to the terminology of Assur graphs as graphs with special properties in rigidity theory. Exploiting the recent works in combinatorial rigidity theory we provide mathematical characterizations of these graphs derived from ‘minimal’ linkages. With these characterizations, we confirm a series of conjectures posed by Offer Shai, and offer techniques and algorithms to be exploited further in future work. [Copyright &y& Elsevier]