A Cut and Branch Approach for the Capacitated <Emphasis Type="Italic">p</Emphasis>-Median Problem Based on Fenchel Cutting Planes

The capacitated p-median problem (CPMP) consists of finding p nodes (the median nodes) minimizing the total distance to the other nodes of the graph, with the constraint that the total demand of the nodes assigned to each median does not exceed its given capacity. In this paper we propose a cutting plane algorithm, based on Fenchel cuts, which allows us to considerably reduce the integrality gap of hard CPMP instances. The formulation strengthened with Fenchel cuts is solved by a commercial MIP solver. Computational results show that this approach is effective in solving hard instances or considerably reducing their integrality gap.      

Exploring Unknown Undirected Graphs

A robot has to construct a complete map of an unknown environment modeled as an undirected connected graph. The task is to explore all nodes and edges of the graph using the minimum number of edge traversals. The penalty of an exploration algorithm running on a graph G = (V(G), E(G)) is the worst-case number of traversals in excess of the lower bound |E(G)| that it must perform in order to explore the entire graph. We give an exploration algorithm whose penalty is O(|V(G)|) for every graph. We also show that some natural exploration algorithms cannot achieve this efficiency.     

The <Emphasis Type="Italic">k</Emphasis>-domatic number of a graph

Let k be a positive integer, and let G be a simple graph with vertex set V (G). A k-dominating set of the graph G is a subset D of V (G) such that every vertex of V (G)-D is adjacent to at least k vertices in D. A k-domatic partition of G is a partition of V (G) into k-dominating sets. The maximum number of dominating sets in a k-domatic partition of G is called the k-domatic number d _k (G). In this paper, we present upper and lower bounds for the k-domatic number, and we establish Nordhaus-Gaddum-type results. Some of our results extend those for the classical domatic number d(G) = d ₁(G).      

An ant colony algorithm for the pos/neg weighted p-median problem

Let a graph G = (V, E) with vertex set V and edge set E be given. The classical graph version of the p-median problem asks for a subset of cardinality p, so that the (weighted) sum of the minimum distances from X to all other vertices in V is minimized. We consider the semi-obnoxious case, where every vertex has either a positive or a negative weight. This gives rise to two different objective functions, namely the weighted sum of the minimum distances from X to the vertices in V\X and, differently, the sum over the minimum weighted distances from X to V\X. In this paper an Ant Colony algorithm with a tabu restriction is designed for both problems. Computational results show its superiority with respect to a previously investigated variable neighborhood search and a tabu search heuristic.This research has partially been supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung.     

Reconstructing shortest paths

This paper develops a polynomial-time algorithm that reconstructs a shortest path between two vertices using only the all pairs shortest path distance matrix. For graphs with positive edge weights, the algorithm requiresO(⦹V|log|V|) time. When the graph contains both positive and negative, but not zero, edge weights, and all cycles have positive length, the algorithm runs inO(|V|²) time. The remarkable feature about the algorithm is that it does not require explicit information about edges in the original graph.     

A fast algorithm for coloring Meyniel graphs

We color the nodes of a graph by first applying successive contractions to non-adjacent nodes until we get a clique; then we color the clique and decontract the graph. We show that this algorithm provides a minimum coloring and a maximum clique for any Meyniel graph by using a simple rule for choosing which nodes are to be contracted. This O(n³) algorithm is much simpler than those already existing for Meyniel graphs. Moreover, the optimality of this algorithm for Meyniel graphs provides an alternate nice proof of the following result of Hoàng: a graph G is Meyniel if and only if, for any induced subgraph of G, each node belongs to a stable set that meets all maximal cliques. Finally we give a new characterization for Meyniel graphs.     

Characterizing defect n-extendable graphs and -critical graphs

A near perfect matching is a matching saturating all but one vertex in a graph. Let G be a connected graph. If any n independent edges in G are contained in a near perfect matching where n is a positive integer and n(|V(G)|-2)/2, then G is said to be defect n-extendable. If deleting any k vertices in G where k|V(G)|-2, the remaining graph has a perfect matching, then G is a k-critical graph. This paper first shows that the connectivity of defect n-extendable graphs can be any integer. Then the characterizations of defect n-extendable graphs and (2k+1)-critical graphs using M-alternating paths are presented.     

Nonstable <Emphasis Type="Italic">K</Emphasis>-theory for Graph Algebras

We compute the monoid V(L _K (E)) of isomorphism classes of finitely generated projective modules over certain graph algebras L _K (E), and we show that this monoid satisfies the refinement property and separative cancellation. We also show that there is a natural isomorphism between the lattice of graded ideals of L _K (E) and the lattice of order-ideals of V(L _K (E)). When K is the field of complex numbers, the algebra is a dense subalgebra of the graph C ^*-algebra C ^*(E), and we show that the inclusion map induces an isomorphism between the corresponding monoids. As a consequence, the graph C*-algebra of any row-finite graph turns out to satisfy the stable weak cancellation property. The first author was partially supported by the DGI and European Regional Development Fund, jointly, through Project BFM2002-01390, the second and the third by the DGI and European Regional Development Fund, jointly, through Project MTM2004-00149 and by PAI III grant FQM-298 of the Junta de Andalucía. Also, the first and third authors are partially supported by the Comissionat per Universitats i Recerca de la Generalitat de Catalunya.     

Extended formulations for the A-cut problem

LetG=(V, E) be an undirected graph andA⊆V. We consider the problem of finding a minimum cost set of edges whose deletion separates every pair of nodes inA. We consider two extended formulations using both node and edge variables. An edge variable formulation has previously been considered for this problem (Chopra and Rao (1991), Cunningham (1991)). We show that the LP-relaxations of the extended formulations are stronger than the LP-relaxation of the edge variable formulation (even with an extra class of valid inequalities added). This is interesting because, while the LP-relaxations of the extended formulations can be solved in polynomial time, the LP-relaxation of the edge variable formulation cannot. We also give a class of valid inequalities for one of the extended formulations. Computational results using the extended formulations are performed.     

Bi‐arc graphs and the complexity of list homomorphisms

Given graphs G, H, and lists L(v) ? V(H), v ε V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) → V(H) such that uv ε E(G) implies f(u)f(v) ε E(H), and f(v) ε L(v) for all v ε V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) ? V(H), v ε V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP‐complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP‐complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi‐arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi‐arc graph, and is NP‐complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61–80, 2003     

Symbolic topological sorting with OBDDs

We present a symbolic OBDD algorithm for topological sorting which requires O(log²|V|) OBDD operations. Then we analyze its true runtime for the directed grid graph and show an upper bound of O(log⁴|V|loglog|V|). This is the first true runtime analysis of a symbolic OBDD algorithm for a fundamental graph problem, and it demonstrates that one can hope that the algorithm behaves well for sufficiently structured inputs.     

<Emphasis Type="Italic">f</Emphasis>-Colorings of some graphs of <Emphasis Type="Italic">f</Emphasis>-class 1

An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v V（G） at most f（v） times. The minimum number of colors needed to f-color G is called the f-chromatic index of G and is denoted by X′f（G）. Any simple graph G has the f-chromatic index equal to △f（G） or △f（G） ＋ 1, where △f（G） =max v V（G）{[d（v）/f（v）]}. If X′f（G） = △f（G）, then G is of f-class 1; otherwise G is of f-class 2. In this paper, a class of graphs of f-class 1 are obtained by a constructive proof. As a result, f-colorings of these graphs with △f（G） colors are given.     

On pitfalls in computing the geodetic number of a graph

Given a simple connected graph G = (V, E) the geodetic closure of a subset S of V is the union of all sets of nodes lying on some geodesic (or shortest path) joining a pair of nodes . The geodetic number, denoted by g(G), is the smallest cardinality of a node set S ^* such that I[S ^*] = V. In “The geodetic number of a graph”, [Harary et al. in Math. Comput. Model. 17:89–95, 1993] propose an incorrect algorithm to find the geodetic number of a graph G. We provide counterexamples and show why the proposed approach must fail. We then develop a 0–1 integer programming model to find the geodetic number. Computational results are given.     

Bi-Objective Median Subtree Location Problems

A number of network design problems can be built on the following premise: given an undirected tree network, T, with node set, V, identify a single subtree, t, containing nodes, v, so that the subtree is located optimally with respect to the remaining, subset of unconnected nodes {V–v}. Distances between unconnected nodes and nodes in the subtree t can be defined on paths that are restricted to lie in the larger tree T (the restricted case), or can be defined on paths in an auxiliary complete graph G (the unrestricted case). The unrestricted case represents a class of problems that is not explicitly recognized in the literature, which is of intermediate complexity relative to the widely studied restricted case, and the general problem in which the underlying graph is general. This paper presents the Median Subtree Location Problem (MSLP), formulated as a bicriterion problem that trades off the cost of a subtree, t, against the population-weighted travel distance from the unconnected nodes to nodes on the subtree where both objectives are to be minimized. Integer programs were formulated for the travel restricted and travel unrestricted cases and were tested using linear programming and branch and bound to resolve fractions. Tradeoff curves between cost and travel burden were developed for sample networks.     

Sparse <Emphasis Type="Italic">H</Emphasis>-Colourable Graphs of Bounded Maximum Degree

Let F be a graph of order at most k. We prove that for any integer g there is a graph G of girth at least g and of maximum degree at most 5k¹³ such that G admits a surjective homomorphism c to F, and moreover, for any F-pointed graph H with at most k vertices, and for any homomorphism h from G to H there is a unique homomorphism f from F to H such that h=fc. As a consequence, we prove that if H is a projective graph of order k, then for any finite family of prescribed mappings from a set X to V(H) (with ||=t), there is a graph G of arbitrary large girth and of maximum degree at most 5k^26mt (where m=|X|) such that and up to an automorphism of H, there are exactly t homomorphisms from G to H, each of which is an extension of an f.Supported in part by the National Science Council under grant NSC89-2115-M-110-012Final version received: June 9, 2003     

The k‐piece packing problem

A k‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k. We consider the problem of covering the maximum number of nodes of a graph by node disjoint k‐pieces. When k = 1 this is the maximum matching problem, and when k = 2 this is the problem, recently studied by Kaneko [ 19 [, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Partitioning planar graphs: a?fast combinatorial approach for max-cut

The max-cut problem asks for partitioning the nodes V of a graph G=(V,E) into two sets (one of which might be empty), such that the sum of weights of edges joining nodes in different partitions is maximum. Whereas for general instances the max-cut problem is NP-hard, it is polynomially solvable for certain classes of graphs. For planar graphs, there exist several polynomial-time methods determining maximum cuts for arbitrary choice of edge weights. Typically, the problem is solved by computing a minimum-weight perfect matching in some associated graph. The most efficient known algorithms are those of Shih et al. (IEEE Trans. Comput. 39(5):694–697, 1990) and that of Berman et al. (WADS, Lecture Notes in Computer Science, vol. 1663, pp. 25–36, Springer, Berlin, 1999). The running time of the former can be bounded by O(|V|^\frac32log|V|)O(|V|^{\frac{3}{2}}\log|V|). The latter algorithm is more generally for determining T-joins in graphs. Although it has a slightly larger bound on the running time of O(|V|^\frac32(log|V|)^\frac32)a(|V|)O(|V|^{\frac{3}{2}}(\log|V|)^{\frac{3}{2}})\alpha(|V|), where α(|V|) is the inverse Ackermann function, it can solve large instances in practice.     

Algorithms for graph partitioning on the planted partition model

The NP‐hard graph bisection problem is to partition the nodes of an undirected graph into two equal‐sized groups so as to minimize the number of edges that cross the partition. The more general graph l‐partition problem is to partition the nodes of an undirected graph into l equal‐sized groups so as to minimize the total number of edges that cross between groups. We present a simple, linear‐time algorithm for the graph l‐partition problem and we analyze it on a random “planted l‐partition” model. In this model, the n nodes of a graph are partitioned into l groups, each of size n/l; two nodes in the same group are connected by an edge with some probability p, and two nodes in different groups are connected by an edge with some probability r<p. We show that if p−r≥n^−1/2+ϵ for some constant ϵ, then the algorithm finds the optimal partition with probability 1− exp(−n^Θ(ε)). © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 116–140, 2001     

Algorithms and Methods for Solving Scheduling Problems and Other Extremum Problems on Large-Scale Graphs

We consider a large-scale directed graph G = (V, E) whose edges are endowed with a family of characteristics. A subset of vertices of the graph, V′ ⊂ V, is selected and some additional conditions are imposed on these vertices. An algorithm for reducing the optimization problem on the graph G to an optimization problem on the graph G′ = (V′, E′) of a lower dimension is developed. The main steps of the solution and some methods for constructing an approximate solution to the problem on the transformed graph G′ are presented.__________Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 9, No. 1, pp. 235–251, 2003.     

Generalized delaunay triangulation for planar graphs

We introduce the notion of generalized Delaunay triangulation of a planar straight-line graphG=(V, E) in the Euclidean plane and present some characterizations of the triangulation. It is shown that the generalized Delaunay triangulation has the property that the minimum angle of the triangles in the triangulation is maximum among all possible triangulations of the graph. A general algorithm that runs inO(|V|²) time for computing the generalized Delaunay triangulation is presented. When the underlying graph is a simple polygon, a divide-and-conquer algorithm based on the polygon cutting theorem of Chazelle is given that runs inO(|V| log |V|) time.Supported in part by the National Science Foundation under Grants DCR 8420814 and ECS 8340031.