On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

Generalizing the modeling of fuzzy logic controllers by parameterized aggregation operators

We describe the type of reasoning used in the typical fuzzy logic controller, the Mamdani reasoning method. We point out the basic assumptions in this model. We discuss the S-OWA operators which provide families of parameterized “andlike” and “orlike” operators. We generalize the Mamdani model by introducing these operators. We introduce a method, which we call Direct Fuzzy Reasoning (DFR), which results from one choice of the parameters. We develop some learning algorithms for the new method. We show how the Takagi-Sugeno-Kang (TSK) method of reasoning is an example of this DFR method.     

A new approach to solving three combinatorial enumeration problems on planar graphs

The purpose of this paper is to show how the technique of delta-wye graph reduction provides an alternative method for solving three enumerative function evaluation problems on planar graphs. In particular, it is shown how to compute the number of spanning trees and perfect matchings, and how to evaluate energy in the Ising “spin glass” model of statistical mechanics. These alternative algorithms require O(n²) arithmetic operations on an n-vertex planar grapha, and are relatively easy to implement.     

Structural filtering: a paradigm for efficient and exact geometric programs

We introduce a new and simple filtering technique that can be used in the implementation of geometric algorithms called “structural filtering”. Using this filtering technique we gain about 20% when compared to predicate-filtered implementations. Of theoretical interest are some results regarding the robustness of sorting algorithms against erroneous comparisons.

There is software support for the concept of structural filtering in LEDA (Library of Efficient Data Types and Algorithms, http://www.mpi-sb.mpg.de/LEDA/leda.html) and CGAL (Computational Geometry Algorithms Library, http://www.cgal.org).     

Comment on “The Steiner number of a graph” by G. Chartrand and P. Zhang: [Discrete Mathematics 242 (2002) 41–54]

We show by counterexample that one of the main results in the paper “The Steiner number of a graph” by Chartrand and Zhang (Disc. Math. 242 (2002) 41–54) does not hold. To be more precise, we prove both that not every Steiner set is a geodetic set and that there are connected graphs whose Steiner number is strictly lower than its geodetic number.     

Landmarks in graphs

Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a “graph space”. The robot can locate itself by the presence of distinctively labeled “landmark” nodes in the graph space. For a robot navigating in Euclidean space, visual detection of a distinctive landmark provides information about the direction to the landmark, and allows the robot to determine its position by triangulation. On a graph, however, there is neither the concept of direction nor that of visibility. Instead, we shall assume that a robot navigating on a graph can sense the distances to a set of landmarks.

Evidently, if the robot knows its distances to a sufficiently large set of landmarks, its position on the graph is uniquely determined. This suggests the following problem: given a graph, what are the fewest number of landmarks needed, and where should they be located, so that the distances to the landmarks uniquely determine the robot's position on the graph? This is actually a classical problem about metric spaces. A minimum set of landmarks which uniquely determine the robot's position is called a “metric basis”, and the minimum number of landmarks is called the “metric dimension” of the graph. In this paper we present some results about this problem. Our main new results are that the metric dimension of a graph with n nodes can be approximated in polynomial time within a factor of O(log n), and some properties of graphs with metric dimension two.     

Multi-step quasi-Newton methods for optimization

Quasi-Newton methods update, at each iteration, the existing Hessian approximation (or its inverse) by means of data deriving from the step just completed. We show how “multi-step” methods (employing, in addition, data from previous iterations) may be constructed by means of interpolating polynomials, leading to a generalization of the “secant” (or “quasi-Newton”) equation. The issue of positive-definiteness in the Hessian approximation is addressed and shown to depend on a generalized version of the condition which is required to hold in the original “single-step” methods. The results of extensive numerical experimentation indicate strongly that computational advantages can accrue from such an approach (by comparison with “single-step” methods), particularly as the dimension of the problem increases.     

Construction of the value function in a pursuit-evasion game with three pursuers and one evader

A differential pursuit-evasion game is considered with three pursuers and one evader. It is assumed that all objects (players) have simple motions and that the game takes place in a plane. The control vectors satisfy geometrical constraints and the evader has a superiority in control resources. The game time is fixed. The value functional is the distance between the evader and the nearest pursuer at the end of the game. The problem of determining the value function of the game for any possible position is solved.

Three possible cases for the relative arrangement of the players at an arbitrary time are studied: “one-after-one”, “two-after-one”, “three-after-one-in-the-middle” and “three-after-one”. For each of the relative arrangements of the players a guaranteed result function is constructed. In the first three cases the function is expressed analytically. In the fourth case a piecewise-programmed construction is presented with one switchover, on the basis of which the value of the function is determined numerically. The guaranteed result function is shown to be identical with the game value function. When the initial pursuer positions are fixed in an arbitrary manner there are four game domains depending on their relative positions. The boundary between the “three-after-one-in-the-middle” domain and the “three-after-one” domain is found numerically, and the remaining boundaries are interior Nicomedean conchoids, lines and circles. Programs are written that construct singular manifolds and the value function level lines.     

On uniform k-partition problems

We study various uniform k-partition problems which consist in partitioning m sets, each of cardinality k, into k sets of cardinality m such that each of these sets contains exactly one element from every original set. The problems differ according to the particular measure of “set uniformity” to be optimized. Most problems are polynomial and corresponding solution algorithms are provided. A few of them are proved to be NP-hard. Examples of applications to scheduling and routing problems are also discussed.     

Mereological relations

A “mereological” relation is one of “part-to-whole” type. This paper proposes a model-theoretic approach to identifying and classifying such relations. Three initial applications of this approach are investigated. In each case, the class of identified relations is found to consist precisely of the partial orders on the underlying set. Further applications are proposed.     

Combinatorial aspects of geometric graphs

As a special case of our main result, we show that for all L> 0, each k-nearest neighbor graph in d dimensions excludes K_h as a depth L minor if h = Ω(L^d). More generally, we prove that the overlap graphs defined by Miller, Teng, Thurston and Vavasis (1993) have this combinatorial property. By a construction of Plotkin, Rao and Smith (1994), our result implies that overlap graphs have “good” cut-covers, answering an open question of Kaklamanis, Krizanc and Rao (1993). Consequently, overlap graphs can be emulated on hypercube graphs with a constant factor of slow-down and on butterfly graphs with a factor of O(log^* n) slow-down. Therefore, computations on overlap graphs, such as finite element and finite difference methods on “well-conditioned” meshes and image processing on k-nearest neighbor graphs, can be performed on hypercubic parallel machines with a linear speed-up. Our result, in conjunction with a result of Plotkin, Rao and Smith, also yields a combinatorial proof that overlap graphs have separators of sublinear size. We also show that with high probability, the Delaunay diagram, the relative neighborhood graph, and the k-nearest neighbor graph of a random point set exclude K_h as a depth L minor if h = Ω(L^d/2 log n).     

Polynomial algorithms that prove an NP-Hard hypothesis implies an NP-hard conclusion

A number of results in hamiltonian graph theory are of the form “ implies ”, where is a property of graphs that is NP-hard and is a cycle structure property of graphs that is also NP-hard. An example of such a theorem is the well-known Chvátal–Erd s Theorem, which states that every graph G with κ is hamiltonian. Here κ is the vertex connectivity of G and is the cardinality of a largest set of independent vertices of G. In another paper Chvátal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than κ independent vertices. In this note we point out that other theorems in hamiltonian graph theory have a similar character. In particular, we present a constructive proof of a well-known theorem of Jung (Ann. Discrete Math. 3 (1978) 129) for graphs on 16 or more vertices.     

Drawing series parallel digraphs symmetrically

In this paper we present algorithms for drawing series parallel digraphs with as much symmetry as possible. The first step is to compute a certain kind of automorphism, called an “upward planar automorphism” for an input series parallel digraph. The next step uses these automorphisms to construct a symmetric drawing of the graph. We present several variations of the second step, with visibility drawings, “bus-orthogonal” drawings, and polyline drawings. All algorithms run in linear time.     

Fuzzy logic in measurements

Our main interest in this paper is to translate from “natural language” into “system theoretical language”. This is of course important since a statement in system theory can be analyzed mathematically or computationally. We assume that, in order to obtain a good translation, “system theoretical language” should have great power of expression. Thus we first propose a new frame of system theory, which includes the concepts of “measurement” as well as “state equation”. And we show that a certain statement in usual conversation, i.e., fuzzy modus ponens with the word “very”, can be translated into a statement in the new frame of system theory. Though our result is merely one example of the translation from “natural language” into “system theoretical language”, we believe that our method is fairly general.     

A generalization of the zero–one principle for sorting algorithms

In this paper a new general approach for the so-called “zero-one principle” for sorting algorithms is described. A theorem from propositional logic that states the connection between two-valued logic and many-valued logic is used to prove this zero-one principle. As a consequence a zero-one principle for a more general class of sorting algorithms is derived.     

Choosability conjectures and multicircuits

This paper starts with a discussion of several old and new conjectures about choosability in graphs. In particular, the list-colouring conjecture, that ch′=χ′ for every multigraph, is shown to imply that if a line graph is (a : b)-choosable, then it is (ta : tb)-choosable for every positive integer t. It is proved that ch(H²)=χ(H²) for many “small” graphs H, including inflations of all circuits (connected 2-regular graphs) with length at most 11 except possibly length 9; and that ch″(C)=χ″(C) (the total chromatic number) for various multicircuits C, mainly of even order, where a multicircuit is a multigraph whose underlying simple graph is a circuit. In consequence, it is shown that if any of the corresponding graphs H² or T(C) is (a : b)-choosable, then it is (ta : tb)-choosable for every positive integer t.     

Geometric quadrisection in linear time, with application to VLSI placement

We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.

This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.

This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips.     

Nondeterministic dynamic programming on a parallel coprocessing system

We describe how nondeterministic dynamic programming (DP) algorithms can be designed for a new class of parallel coprocessing systems using “functional memory”, an architecture based upon dataflow computer principles. We also show how Petri nets can be used to model and express such parallel DP algorithms. Finally, we discuss architectural improvements that would facilitate the processing of Petri net models of nondeterministic DP algorithms on functional memory computers (FMC).     

The Dempster–Shafer calculus for statisticians

The Dempster–Shafer (DS) theory of probabilistic reasoning is presented in terms of a semantics whereby every meaningful formal assertion is associated with a triple (p, q, r) where p is the probability “for” the assertion, q is the probability “against” the assertion, and r is the probability of “don’t know”. Arguments are presented for the necessity of “don’t know”. Elements of the calculus are sketched, including the extension of a DS model from a margin to a full state space, and DS combination of independent DS uncertainty assessments on the full space. The methodology is applied to inference and prediction from Poisson counts, including an introduction to the use of join-tree model structure to simplify and shorten computation. The relation of DS theory to statistical significance testing is elaborated, introducing along the way the new concept of “dull” null hypothesis.     

Planar and axially symmetric configurations which are circumvented with the maximum critical mach number

The structure of planar and axially symmetric configurations which, by satisfying a number of geometrical constraints, are circumvented in a boundless space or in a cylindrical channel by an ideal (non-viscous and non-thermally conducting) gas with a maximal critical Mach number M* is found. The analysis is carried out using the “rectilinearity property” of a sonic line in “subsonic” flows (SF), the “principle of a maximum” for an SF and “comparison theorems” which are either taken from /1/ or serve as a generalization of the corresponding assertions from /1/. Following /1/, configurations are considered which have a plane or axis of symmetry parallel to the velocity V_∞ of the approach stream, while flows in which (including the boundary) the Mach number M 1 are said to be “subsonic”. As usual, by M* we mean a value of M_∞ such that the inequality M1, which is satisfied in the whole stream when M_∞ M*, is violated when M_∞>M*.

The configurations investigated include closed bodies and the leading (trailing) parts of a semi-infinite plate or a circular cylinder in an unbounded flow and in a channel as well as lattices of symmetric profiles. Both in /1/, where the structure of closed planar and axially symmetric bodies was found, as well as in /2/, where such bodies were constructed numerically, the generatrices of all the configurations investigated contain the end planes or the segments replacing them of the maximum permissible slope (in modulus) and the “free” streamlines with M 1. Now, however, unlike in /1, 2/, segments of the horizontals are added to it in the general case. Furthermore, in the case of flows in channels and lattices, the configurations which have been found can be circumvented with the development of finite domains of advancing sonic flow.