Search

Fault diagnosis of interconnection networks is vital to ensuring the reliability and maintenance of multiprocessor systems. Based on graph theory, diagnostic algorithms for solving the problem of fault diagnosis in interconnection networks have been widely studied. As the number of processors in multiprocessor systems has increased in recent years, fault diagnosis algorithms based on graph theory cannot meet the current diagnosis requirements of some interconnection networks, such as t-diagnosable systems. In this paper, we use the evolution diagnosis approach to study fault diagnosis in t-diagnosable systems under the PMC model. First, for a t-diagnosable system G with a syndrome σ , we use a simple centralized algorithm to generate its simplified diagnosis graph G f , which contains all the faulty nodes in G. Based on the graph, we prove that the faulty node set in G is the minimum cover set of G f . Next, we prove that the problem of computing the minimum cover set for G f is equivalent to the problem of computing the optimal solution of a zero-one integer program. Using this result, we propose a novel genetic algorithm to solve the problem of the zero-one integer program. The simulation results show that the diagnostic accuracy of our proposed algorithm is equal to or greater than 96% and that the proposed algorithm outperforms its competitors in terms of diagnostic accuracy, number of iterations and running time. [ABSTRACT FROM AUTHOR]

In this paper, using the properties of graph convergence of H(.,.)-accretive operators, we construct a perturbed algorithm for solving systems of ill-posed variational inclusions involving H(.,.)-accretive operators. Under some suitable conditions, we prove that the sequence generated by the proposed method is strongly convergent to the unique solution of the problem. The main results presented in this paper generalize and improve some recent results in the literature. [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: 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]

Let G = (V, E) be a connected simple graph and let M be a nonempty subset of V. The M-distance pattern of a vertex u in G is the set of all distances from u to the vertices in M. If the distance patterns of all vertices in V are distinct, then the set Mis a distance pattern distinguishing set of G. A graph G with a distance pattern distinguishing set is called a distance pattern distinguishing graph. Minimum number of vertices in a distance pattern distinguishing set is called distance pattern distinguishing number of a graph. This paper initiates a study on the problem of finding distance pattern distinguishing number of a graph and gives bounds for distance pattern distinguishing number. Further, this paper provides an algorithm to determine whether a graph is a distance pattern distinguishing graph or not and hence to determine the distance pattern distinguishing number of that graph. [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]

Abstract: In this paper, we study the geodetic convexity of graphs, focusing on the problem of the complexity of computing a minimum hull set of a graph in several graph classes. For any two vertices of a connected graph , the closed interval of and is the set of vertices that belong to some shortest -path. For any , let . A subset is geodesically convex or convex if . In other words, a subset is convex if, for any and for any shortest -path , . Given a subset , the convex hull of is the smallest convex set that contains . We say that is a hull set of if . The size of a minimum hull set of is the hull number of , denoted by . The Hull Number problem is to decide whether , for a given graph and an integer . Dourado et al. showed that this problem is NP-complete in general graphs. In this paper, we answer an open question of Dourado et al. (2009) [1] by showing that the Hull Number problem is NP-hard even when restricted to the class of bipartite graphs. Then, we design polynomial-time algorithms to solve the Hull Number problem in several graph classes. First, we deal with the class of complements of bipartite graphs. Then, we generalize some results in Araujo et al. (2011) [2] to the class of -graphs and to cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an -node graph without simplicial vertices is at most in general, at most if is regular or has no triangle, and at most if has girth at least . [Copyright &y& Elsevier]

In this paper a new graph-based evolutionary algorithm, gM-PAES, is proposed in order to solve the complex problem of truss layout multi-objective optimization. In this algorithm a graph-based genotype is employed as a modified version of Memetic Pareto Archive Evolution Strategy (M-PAES), a well-known hybrid multi-objective optimization algorithm, and consequently, new graph-based crossover and mutation operators perform as the solution generation tools in this algorithm. The genetic operators are designed in a way that helps the multi-objective optimizer to cover all parts of the true Pareto front in this specific problem. In the optimization process of the proposed algorithm, the local search part of gM-PAES is controlled adaptively in order to reduce the required computational effort and enhance its performance. In the last part of the paper, four numeric examples are presented to demonstrate the performance of the proposed algorithm. Results show that the proposed algorithm has great ability in producing a set of solutions which cover all parts of the true Pareto front. [ABSTRACT FROM AUTHOR]

Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits k and the maximum degree r are taken together as a combined parameter, the problems are tractable (i.e. in FPT ), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural k + r parameterization. [ABSTRACT FROM AUTHOR]

Abstract: In recent years, the use of extensible processors has been increased. Extensible processors extend the base instruction set of a general-purpose processor with a set of custom instructions. Custom instructions that can be implemented in special hardware units make it possible to improve performance and decrease power consumption in extensible processors. The key issue involved is to generate and select automatically the custom instructions from a high-level application code. In this paper, we propose a new efficient algorithm for the automatic generation of all candidate instructions (or patterns). Our pattern generation algorithm identify all feasible connected and disjoint patterns under different constraints. Compared to a previously proposed well-known algorithm, our algorithm solves the problem more efficiently by taking advantage of the topological property of data flow graph (DFG) as well as overcoming the drawbacks of the previously proposed algorithm. An extension of the proposed algorithm is also presented in this paper. The extended algorithm further radically reduce the search space by considering the input resolving nodes. Experimental results show that our algorithms can achieve orders of magnitude speedup over the well-know algorithm. [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]

Graceful labeling is one of the best known labeling methods of graphs. Despite the large number of papers published on the subject of graph labeling, there are few particular techniques to be used by researchers to gracefully label graphs. In this paper, first a new approach based on the mathematical programming technique is presented to model the graceful labeling problem. Then a "branching method" is developed to solve the problem for special classes of graphs. Computational results show the efficiency of the proposed algorithm for different classes of graphs. One of the interesting results of our model is in the class of trees. The largest tree known to be graceful has at most 27 vertices but our model can easily solve the graceful labeling for trees with 40 vertices. [ABSTRACT FROM AUTHOR]

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

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

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

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

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

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]

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

In this paper, we revisit the much studied problem of Pattern Matching with Swaps (Swap Matching problem, for short). We first present a graph-theoretic model, which opens a new and so far unexplored avenue to solve the problem. Then, using the model, we devise two efficient algorithms to solve the swap matching problem. The resulting algorithms are adaptations of the classic shift-and algorithm. For patterns having length similar to the word-size of the target machine, both the algorithms run in linear time considering a fixed alphabet. [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]

The \(k\) -core decomposition in a graph is a fundamental problem for social network analysis. The problem of \(k\) -core decomposition is to calculate the core number for every node in a graph. Previous studies mainly focus on \(k\) -core decomposition in a static graph. There exists a linear time algorithm for \(k\) -core decomposition in a static graph. However, in many real-world applications such as online social networks and the Internet, the graph typically evolves over time. In such applications, a key issue is to maintain the core numbers of nodes when the graph changes over time. A simple implementation is to perform the linear time algorithm to recompute the core number for every node after the graph is updated. Such simple implementation is expensive when the graph is very large. In this paper, we propose a new efficient algorithm to maintain the core number for every node in a dynamic graph. Our main result is that only certain nodes need to update their core numbers when the graph is changed by inserting/deleting an edge. We devise an efficient algorithm to identify and recompute the core numbers of such nodes. The complexity of our algorithm is independent of the graph size. In addition, to further accelerate the algorithm, we develop two pruning strategies by exploiting the lower and upper bounds of the core number. Finally, we conduct extensive experiments over both real-world and synthetic datasets, and the results demonstrate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

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

This paper considers the problem of clustering a partially observed unweighted graph--i.e., one where for some node pairs we know there is an edge between them, for some others we know there is no edge, and for the remaining we do not know whether or not there is an edge. We want to organize the nodes into disjoint clusters so that there is relatively dense (observed) connectivity within clusters, and sparse across clusters. We take a novel yet natural approach to this problem, by focusing on finding the clustering that minimizes the number of "disagreements"--i.e., the sum of the number of (observed) missing edges within clusters, and (observed) present edges across clusters. Our algorithm uses convex optimization; its basis is a reduction of disagreement minimization to the problem of recovering an (unknown) low-rank matrix and an (unknown) sparse matrix from their partially observed sum. We evaluate the performance of our algorithm on the classical Planted Partition/Stochastic Block Model. Our main theorem provides sufficient conditions for the success of our algorithm as a function of the minimum cluster size, edge density and observation probability; in particular, the results characterize the tradeoff between the observation probability and the edge density gap. When there are a constant number of clusters of equal size, our results are optimal up to logarithmic factors. [ABSTRACT FROM AUTHOR]

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

In biological systems, the dynamic analysis method has gained increasing attention in the past decade. The Boolean network is the most common model of a genetic regulatory network. The interactions of activation and inhibition in the genetic regulatory network are modeled as a set of functions of the Boolean network, while the state transitions in the Boolean network reflect the dynamic property of a genetic regulatory network. A difficult problem for state transition analysis is the finding of attractors. In this paper, we modeled the genetic regulatory network as a Boolean network and proposed a solving algorithm to tackle the attractor finding problem. In the proposed algorithm, we partitioned the Boolean network into several blocks consisting of the strongly connected components according to their gradients, and defined the connection between blocks as decision node. Based on the solutions calculated on the decision nodes and using a satisfiability solving algorithm, we identified the attractors in the state transition graph of each block. The proposed algorithm is benchmarked on a variety of genetic regulatory networks. Compared with existing algorithms, it achieved similar performance on small test cases, and outperformed it on larger and more complex ones, which happens to be the trend of the modern genetic regulatory network. Furthermore, while the existing satisfiability-based algorithms cannot be parallelized due to their inherent algorithm design, the proposed algorithm exhibits a good scalability on parallel computing architectures. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the online tree node assignment problem, which is a generalization of the well studied OVSF code assignment problem. Assigned nodes in a complete binary tree must follow the rule that each leaf-to-root path must contain at most one assigned node. At times, it is necessary to swap assigned nodes with unassigned nodes in order to accommodate some new node assignment. The target of this problem is to minimize the number of swaps in satisfying a sequence of node assignments and releases. This problem is fundamental, not only to the OVSF code assignment, but also to other applications, such as buddy memory allocation and hypercube subcube allocation. All the previous solutions to this problem are based on a sorted and compact configuration by assigning the nodes linearly and level by level, ignoring the intrinsic tree property in their assignments. Our contributions are: (1) give the concept of safe assignment, which is proved to be unique for any fixed set of node-assignment requests; (2) an 8-competitive algorithm by holding the safe assignment; and (3) an improved 6-competitive variant of this algorithm. Our algorithms are simple and easy to implement and our contributions represent meaningful improvements over recent results. [Copyright &y& Elsevier]

This paper considers construction algorithms for the topological 2-D drawing of a graph. These algorithms allow to store, describe and modify the existing information on the drawing of a graph. Finally, we introduce necessary notions and structures to solve the problem of the topological 2-D drawing of a graph. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study an interesting geometric partition problem, called optimal field splitting, which arises in Intensity-Modulated Radiation Therapy (IMRT). In current clinical practice, a multi-leaf collimator (MLC) with a maximum leaf spread constraint is used to deliver the prescribed intensity maps (IMs). However, the maximum leaf spread of a MLC may require to split a large intensity map into several overlapping sub-IMs with each being delivered separately. We develop a close-to-linear time algorithm for solving the field splitting problem while minimizing the total complexity of the resulting sub-IMs, thus improving the treatment delivery efficiency. Meanwhile, our algorithm strives to minimize the maximum beam-on time of those sub-IMs. Our basic idea is to formulate the field splitting problem as computing a shortest path in a directed acyclic graph, which expresses a special “layered” structure. The edge weights of the graph satisfy the Monge property, which enables us to solve this shortest path problem by examining only a small portion of the graph, yielding a close-to-linear time algorithm. To minimize the maximum beam-on time of the resulting sub-IMs, we consider an interesting min–max slope path problem in a monotone polygon which is solvable in linear time. The min–max slope path problem may be of interest in its own right. Experimental results based on real medical data and computer generated IMs showed that our new algorithm runs fast and produces high quality field splitting results. [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]

Level-sensitive latches are widely used in high-performance designs. For such circuits, efficient statistical timing analysis algorithms are needed to take increasing process variations into account. The existing methods for solving this problem are still computationally expensive and can only provide the yield at a given clock period. In this paper, we propose a method combining reduced iterations and graph transformations. The reduced iterations extract setup time constraints and identify a subgraph for the following graph transformations handling the constraints from nonpositive loops. The combined algorithms are very efficient, more than ten times faster than other existing methods, and result in a parametric minimum clock period, which, together with the hold-time constraints, can be used to compute the yield at any given clock period very easily. [ABSTRACT FROM AUTHOR]

This paper describes a generic branch-and-cut algorithm applicable to the solution of multiobjective optimization problems for which a lower bound can be defined as a polynomially solvable multiobjective problem. The algorithm closely follows standard branch and cut except for the definition of the lower and upper bounds and some optional speed-up mechanisms. It is applied to a routing problem called the multilabel traveling salesman problem, a variant of the traveling salesman problem in which labels are attributed to the edges. The goal is to find a Hamiltonian cycle that minimizes the tour length and the number of labels in the tour. Implementations of the generic multiobjective branch-and-cut algorithm and speed-up mechanisms are described. Computational experiments are conducted, and the method is compared to the classical ∈-constraint method. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider the checkpoint problem. The input consists of an undirected graph , a set of source–destination pairs , and a collection of paths connecting the pairs. A feasible solution is a multicut , namely, a set of edges whose removal disconnects every source–destination pair. For each we define . In the sum checkpoint (SCP) problem the goal is to minimize , while in the maximum checkpoint (MCP) problem the goal is to minimize . These problems have several natural applications, e.g., in urban transportation and network security. In a sense, they combine the multicut problem and the minimum membership set cover problem. For the sum objective we show that weighted SCP is equivalent, with respect to approximability, to undirected multicut. Thus there exists an approximation for SCP in general graphs. Our current approximability results for the max objective have a wide gap: we provide an approximation factor of for MCP and a hardness of 2 under the assumption . The hardness holds for trees. This solves an open problem of Nelson (2009) . We complement the lower bound by an almost matching upper bound with an asymptotic approximation factor of 2. On trees with all having an ancestor–descendant relation, we give a combinatorial exact algorithm. Besides the algorithm being combinatorial, its running time improves by many orders of magnitude the LP algorithm that follows from total unimodularity. Finally, we show strong hardness for the well-known problem of finding a path with minimum forbidden pairs, which in a sense can be considered the dual to the checkpoint problem. Despite various works on this problem, hardness of approximation was not known prior to this work. We show that the problem cannot be approximated within for some constant , unless . This is the strongest type of hardness possible. It carries over to directed acyclic graphs and is a huge improvement over the plain -hardness of Gabow [H.N. Gabow, Finding paths and cycles of superpolylogarithmic length, SIAM J. Comput. 36 (6) (2007) 1648–1671]. [Copyright &y& Elsevier]

Abstract: A star-shaped drawing of a plane graph is a straight-line drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. In this paper, given a biconnected plane graph with fixed plane embedding and a prescribed set of concave corners, we study the following two problems on star-shaped drawings. First, we consider the problem of finding a star-shaped drawing of such that only prescribed corners are allowed to become concave corners in . More specifically, we characterize a necessary and sufficient condition for a subset of prescribed corners to admit such a star-shaped drawing of . Our characterization includes Thomassen’s characterization of biconnected plane graphs with a prescribed boundary that have convex drawings . We also give a linear-time testing algorithm to test such conditions. Next, given a non-negative cost for each corner in , we show that a star-shaped drawing of with the minimum cost can be found in linear-time, where the cost of a drawing is defined by the sum of costs of concave corners in the drawing. [Copyright &y& Elsevier]

Abstract: In this paper we consider imprecise terrains, that is, triangulated terrains with a vertical error interval in the vertices. In particular, we study the problem of removing as many local extrema (minima and maxima) as possible from the terrain; that is, finding an assignment of one height to each vertex, within its error interval, so that the resulting terrain has minimum number of local extrema. We show that removing only minima or only maxima can be done optimally in time, for a terrain with n vertices. Interestingly, however, the problem of finding a height assignment that minimizes the total number of local extrema (minima as well as maxima) is NP-hard, and is even hard to approximate within a factor of unless . Moreover, we show that even a simplified version of the problem where we can have only three different types of intervals for the vertices is already NP-hard, a result we obtain by proving hardness of a special case of 2-Disjoint Connected Subgraphs, a problem that has lately received considerable attention from the graph-algorithms community. [Copyright &y& Elsevier]

Route planning in large-scale time-dependent road networks is an important practical application of the shortest-path problem that greatly benefits from speedup techniques. In this paper, we extend a two-level hierarchical approach for point-to-point shortest-path computations to the time-dependent case. This method, also known as core routing in the literature for static graphs, consists of the selection of a small subnetwork where most of the computations can be carried out, thus reducing the search space. We combine this approach with bidirectional goal-directed search to obtain an algorithm capable of finding shortest paths in a matter of milliseconds on continental-sized networks. Moreover, we tackle the dynamic scenario where the piecewise linear functions that we use to model time-dependent arc costs are not fixed but can have their coefficients updated requiring only a small computational effort. [ABSTRACT FROM AUTHOR]

This paper presents an arc-based formulation of hydropower reservoir operation problems for application to ant colony optimization algorithms (ACOAs). The search space of the hydropower reservoir operation problem is defined as a partially connected graph composed of a set of arcs connecting the nodes of the graph. Each arc is defined such that it represents a local operation policy of the reservoir. The advantages offered by the proposed formulation are twofold. First, the formulation allows for a straightforward definition of heuristic information, a useful component of the ant-based algorithms, which is not present in other possible formulations of the problem. Second and more importantly, the proposed formulation paves the way for the efficient exploitation of the incremental solution-building mechanism inherent in ant algorithms to explicitly enforce problem constraints. A series of constrained formulations of the ACOA are, therefore, developed and used for the solution of single and multi-reservoir operation problems. The results indicate the ability of the proposed methods, and in particular the constrained versions, to optimally solve large-scale hydropower reservoir operation problems. [ABSTRACT FROM AUTHOR]

This paper presents an efficient algorithm for solving the dynamic user equilibrium (DUE) traffic assignment with a one-to-many origin-destination (OD) pattern. To achieve the efficiency of the algorithm, we employ the following three strategies. First,we exploit the decomposition property of the DUE assignment with respect to the departure time from an origin; we consider the algorithm that solves each of the decomposed DUE assignments sequentially. Second, we represent the decomposed DUE assignment by an arc-node formulation, not by using path variables. Third, we take advantage of the fact that the decomposed DUE assignment reduces to (finite dimensional) nonlinear complementarity problems (NCPs); we develop the algorithm based on the globally convergent Newton's method for general NCPs. These strategies, together with graph theoretic devices, enable us to design a new algorithm which does not require path enumeration and is capable of dealing with very large-scale networks. Numerical experiments disclose that the proposed algorithm solves the DUE assignment very rapidly, even in large-scale networks with some thousands of links and nodes where conventional heuristic algorithms do not converge to the accurate equilibrium solution. [ABSTRACT FROM AUTHOR]