Average‐case analyses of first fit and random fit bin packing

We prove that the First Fit bin packing algorithm is stable under the input distribution U{k−2, k} for all k≥3, settling an open question from the recent survey by Coffman, Garey, and Johnson [“Approximation algorithms for bin backing: A survey,” Approximation algorithms for NP‐hard problems, D. Hochbaum (Editor), PWS, Boston, 1996]. Our proof generalizes the multidimensional Markov chain analysis used by Kenyon, Sinclair, and Rabani to prove that Best Fit is also stable under these distributions [Proc Seventh Annual ACM‐SIAM Symposium on Discrete Algorithms, 1995, pp. 351–358]. Our proof is motivated by an analysis of Random Fit, a new simple packing algorithm related to First Fit, that is interesting in its own right. We show that Random Fit is stable under the input distributions U{k−2, k}, as well as present worst case bounds and some results on distributions U{k−1, k} and U{k, k} for Random Fit. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 240–259, 2000     

On the complexity of finding paths in a two‐dimensional domain I: Shortest paths

The computational complexity of finding a shortest path in a two‐dimensional domain is studied in the Turing machine‐based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial‐time computable two‐dimensional domains: (A) domains with polynomialtime computable boundaries, and (B) polynomial‐time recognizable domains with polynomial‐time computable distance functions. It is proved that the shortest path problem has the polynomial‐space upper bound for domains of both type (A) and type (B); and it has a polynomial‐space lower bound for the domains of type (B), and has a #P lower bound for the domains of type (A). (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Minimum vertex‐diameter‐2‐critical graphs

We prove that the minimum number of edges in a vertex‐diameter‐2‐critical graph on n ≥ 23 vertices is (5n ? 17)/2 if n is odd, and is (5n/2) ? 7 if n is even. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

Recognizing connectedness from vertex‐deleted subgraphs

Let G be a graph of order n. The vertex‐deleted subgraph G ? v, obtained from G by deleting the vertex v and all edges incident to v, is called a card of G. Let H be another graph of order n, disjoint from G. Then the number of common cards of G and H is the maximum number of disjoint pairs (v, w), where v and w are vertices of G and H, respectively, such that G ? v?H ? w. We prove that if G is connected and H is disconnected, then the number of common cards of G and H is at most ?n/2? + 1. Thus, we can recognize the connectedness of a graph from any ?n/2? + 2 of its cards. Moreover, we completely characterize those pairs of graphs that attain the upper bound and show that, with the exception of six pairs of graphs of order at most 7, any pair of graphs that attains the maximum is in one of four infinite families. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:285‐299, 2011     

On the average‐case complexity of Shellsort

We prove a lower bound expressed in the increment sequence on the average‐case complexity of the number of inversions of Shellsort. This lower bound is sharp in every case where it could be checked. A special case of this lower bound yields the general Jiang‐Li‐Vitányi lower bound. We obtain new results, for example, determining the average‐case complexity precisely in the Yao‐Janson‐Knuth 3‐pass case.     

Constructing cubic edge‐ but not vertex‐transitive graphs

An infinite family of cubic edge‐transitive but not vertex‐transitive graphs with edge stabilizer isomorphic to ℤ₂ is constructed. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 152–160, 2000     

Tetravalent vertex‐transitive graphs of order 4p

A graph is vertex‐transitive if its automorphism group acts transitively on vertices of the graph. A vertex‐transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this article, the tetravalent vertex‐transitive non‐Cayley graphs of order 4p are classified for each prime p. As a result, there are one sporadic and five infinite families of such graphs, of which the sporadic one has order 20, and one infinite family exists for every prime p>3, two families exist if and only if p≡1 (mod 8) and the other two families exist if and only if p≡1 (mod 4). For each family there is a unique graph for a given order. © 2011 Wiley Periodicals, Inc.     

Cubic vertex‐transitive graphs of order 2pq

A graph is vertex?transitive or symmetric if its automorphism group acts transitively on vertices or ordered adjacent pairs of vertices of the graph, respectively. Let G be a finite group and S a subset of G such that 1?S and S={s^?1 | s∈S}. The Cayleygraph Cay(G, S) on G with respect to S is defined as the graph with vertex set G and edge set {{g, sg} | g∈G, s∈S}. Feng and Kwak [J Combin Theory B 97 (2007), 627–646; J Austral Math Soc 81 (2006), 153–164] classified all cubic symmetric graphs of order 4p or 2p² and in this article we classify all cubic symmetric graphs of order 2pq, where p and q are distinct odd primes. Furthermore, a classification of all cubic vertex‐transitive non‐Cayley graphs of order 2pq, which were investigated extensively in the literature, is given. As a result, among others, a classification of cubic vertex‐transitive graphs of order 2pq can be deduced. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 285–302, 2010     

Dynamic complexity of optimal paths and discount factors for strongly concave problems

We study the relationship between the dynamical complexity of optimal paths and the discount factor in general infinite-horizon discrete-time concave problems. Given a dynamic systemx _t+1=h(x _t ), defined on the state space, we find two discount factors 0 < ^{* **} < 1 having the following properties. For any fixed discount factor 0 < < ^*, the dynamic system is the solution to some concave problem. For any discount factor ^** < < 1, the dynamic system is not the solution to any strongly concave problem. We prove that the upper bound ^** is a decreasing function of the topological entropy of the dynamic system. Different upper bounds are also discussed.This research was partially supported by MURST, National Group on Nonlinear dynamics in Economics and Social Sciences. The author would like to thank two anonymous referees for helpful comments and suggestions.     

Large families of mutually embeddable vertex‐transitive graphs

For each infinite cardinal κ, we give examples of 2^κ many non‐isomorphic vertex‐transitive graphs of order κ that are pairwise isomorphic to induced subgraphs of each other. We consider examples of graphs with these properties that are also universal, in the sense that they embed all graphs with smaller orders as induced subgraphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 99–106, 2003     

One‐factorizations of complete graphs with vertex‐regular automorphism groups

We consider one‐factorizations of K_2n possessing an automorphism group acting regularly (sharply transitively) on vertices. We present some upper bounds on the number of one‐factors which are fixed by the group; further information is obtained when equality holds in these bounds. The case where the group is dihedral is studied in some detail, with some non‐existence statements in case the number of fixed one‐factors is as large as possible. Constructions both for dihedral groups and for some classes of abelian groups are given. © 2002 John Wiley & Sons, Inc. J Combin Designs 10: 1–16, 2002     

Convergence analysis of a vertex‐centered finite volume scheme for a copper heap leaching model

In this paper a two‐dimensional solute transport model is considered to simulate the leaching of copper ore tailing using sulfuric acid as the leaching agent. The mathematical model consists in a system of differential equations: two diffusion–convection‐reaction equations with Neumann boundary conditions, and one ordinary differential equation. The numerical scheme consists in a combination of finite volume and finite element methods. A Godunov scheme is used for the convection term and an P1‐FEM for the diffusion term. The convergence analysis is based on standard compactness results in L². Some numerical examples illustrate the effectiveness of the scheme. Copyright © 2009 John Wiley & Sons, Ltd.     

An infinite series of regular edge‐ but not vertex‐transitive graphs

Let n be an integer and q be a prime power. Then for any 3 ≤ n ≤ q?1, or n=2 and q odd, we construct a connected q‐regular edge‐but not vertex‐transitive graph of order 2qⁿ⁺¹. This graph is defined via a system of equations over the finite field of q elements. For n=2 and q=3, our graph is isomorphic to the Gray graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 249–258, 2002     

Circular flows of nearly Eulerian graphs and vertex‐splitting

The odd edge connectivity of a graph G, denoted by λ_o(G), is the size of a smallest odd edge cut of the graph. Let S be any given surface and ? be a positive real number. We proved that there is a function f_S(?) (depends on the surface S and lim_?→0 f_S(?)=∞) such that any graph G embedded in S with the odd‐edge connectivity at least f_S(?) admits a nowhere‐zero circular (2+?)‐flow. Another major result of the work is a new vertex splitting lemma which maintains the old edge connectivity and graph embedding. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 147–161, 2002     

On the parallel complexity of hierarchical clustering and CC‐complete problems

Complex data sets are often unmanageable unless they can be subdivided and simplified in an intelligent manner. Clustering is a technique that is used in data mining and scientific analysis for partitioning a data set into groups of similar or nearby items. Hierarchical clustering is an important and well‐studied clustering method involving both top‐down and bottom‐up subdivisions of data. In this article we address the parallel complexity of hierarchical clustering. We describe known sequential algorithms for top‐down and bottom‐up hierarchical clustering. The top‐down algorithm can be parallelized, and when there are n points to be clustered, we provide an O(log n)‐time, n²‐processor Crew Pram algorithm that computes the same output as its corresponding sequential algorithm. We define a natural decision problem based on bottom‐up hierarchical clustering, and add this HIERARCHICAL CLUSTERING PROBLEM (HCP) to the slowly growing list of CC‐complete problems, thereby showing that HCP is one of the computationally most difficult problems in the COMPARATOR CIRCUIT VALUE PROBLEM class. This class contains a variety of interesting problems, and now for the first time a problem from data mining as well. By proving that HCP is CC‐complete, we have demonstrated that HCP is very unlikely to have an NC algorithm. This result is in sharp contrast to the NC algorithm which we give for the top‐down sequential approach, and the result surprisingly shows that the parallel complexities of the top‐down and bottom‐up approaches are different, unless CC equals NC. In addition, we provide a compendium of all known CC‐complete problems. © 2008 Wiley Periodicals, Inc. Complexity, 2008     

Primitivity and independent sets in direct products of vertex‐transitive graphs

We introduce the concept of the primitivity of independent set in vertex‐transitive graphs, and investigate the relationship between the primitivity and the structure of maximum independent sets in direct products of vertex‐transitive graphs. As a consequence of our main results, we positively solve an open problem related to the structure of independent sets in powers of vertex‐transitive graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 218‐225, 2011     

On the complexity of the disjoint paths problem

In this paper we consider the disjoint paths problem. Given a graphG and a subsetS of the edge-set ofG the problem is to decide whether there exists a family of disjoint circuits inG each containing exactly one edge ofS such that every edge inS belongs to a circuit inC. By a well-known theorem of P. Seymour the edge-disjoint paths problem is polynomially solvable for Eulerian planar graphsG. We show that (assumingPNP) one can drop neither planarity nor the Eulerian condition onG without losing polynomial time solvability. We prove theNP-completeness of the planar edge-disjoint paths problem by showing theNP-completeness of the vertex disjoint paths problem for planar graphs with maximum vertex-degree three. This disproves (assumingPNP) a conjecture of A. Schrijver concerning the existence of a polynomial time algorithm for the planar vertex-disjoint paths problem. Furthermore we present a counterexample to a conjecture of A. Frank. This conjecture would have implied a polynomial algorithm for the planar edge-disjoint paths problem. Moreover we derive a complete characterization of all minorclosed classes of graphs for which the disjoint paths problem is polynomially solvable. Finally we show theNP-completeness of the half-integral relaxation of the edge-disjoint paths problem. This implies an answer to the long-standing question whether the edge-disjoint paths problem is polynomially solvable for Eulerian graphs.Supported by Sonderforschungsbereich 303 (DFG)     

On the complexity of Slater’s problems

Given a tournament T, Slater’s problem consists in determining a linear order (i.e. a complete directed graph without directed cycles) at minimum distance from T, the distance between T and a linear order O being the number of directed edges with different orientations in T and in O. This paper studies the complexity of this problem and of several variants of it: computing a Slater order, computing a Slater winner, checking that a given vertex is a Slater winner and so on.