The treewidth and pathwidth of hypercubes

The d-dimensional hypercube, H_d, is the graph on 2^d vertices, which correspond to the 2^dd-vectors whose components are either 0 or 1, two of the vertices being adjacent when they differ in just one coordinate. The notion of Hamming graphs (denoted by ) generalizes the notion of hypercubes: The vertices correspond to the q^dd-vectors where the components are from the set {0,1,2,…,q-1}, and two of the vertices are adjacent if and only if the corresponding vectors differ in exactly one component. In this paper we show that the and the .     

The structure of obstructions to treewidth and pathwidth

It is known that the class of graphs with treewidth (resp. pathwidth) bounded by a constant w can be characterized by a finite obstruction set obs(TW(w)) (resp. obs(PW(w))). These obstruction sets are known for w3 so far. In this paper we give a structural characterization of graphs from obs(TW(w)) (resp. obs(PW(w))) with a fixed number of vertices in terms of subgraphs of the complement. Our approach also essentially simplifies known characterization of graphs from obs(TW(w)) (resp. obs(PW(w))) with (w+3) vertices.

Also for any w3 a graph from obs(TW(w))obs(PW(w)) is constructed, that solves an open problem.     

Bandwidth and pathwidth of three-dimensional grids

We study the bandwidth and the pathwidth of multi-dimensional grids. It can be shown for grids, that these two parameters are equal to a more basic graph parameter, the vertex boundary width. Using this fact, we determine the bandwidth and the pathwidth of three-dimensional grids, which were known only for the cubic case. As a by-product, we also determine the two parameters of multi-dimensional grids with relatively large maximum factors.     

ContributionsAn algorithm for the Tutte polynomials of graphs of bounded treewidth

Let k be a fixed, positive integer. We give an algorithm which computes the Tutte polynomial of any graph G of treewidth at most k in time O(n^{2+7 log₂ c}), where c is twice the number of partitions of a set with 3k + 3 elements and n the number of vertices of G.     

Digraph searching, directed vertex separation and directed pathwidth

The four digraph search models, directed search, undirected search, strong search, and weak search, are studied in this paper. There are three types of actions for searchers in these models: placing, removing, and sliding. The four models differ in the abilities of searchers and intruders depending on whether or not they must obey the edge directions when they move along the directed edges. In this paper, we investigate the relationships between these search models. We introduce the concept of directed vertex separation for digraphs. We also discuss the properties of directed vertex separation, and investigate the relations between directed vertex separation, directed pathwidth and search numbers in different search models.     

The best one-sided approximation of one class of functions by another

We concern ourselves with problems of the best one-sided approximation of classes of continuous functions. We obtain estimates of the best one-sided approximation of one class of functions by another, and we find exact values of the upper bounds of the best one-sided approximations on the classes H of 2-periodic functions [given by an arbitrary convex modulus of continuity(t)] by trigonometric polynomials of order not higher thann–1 in the L₂ metric.Translated from Matematicheskie Zametki, Vol. 14, No. 5, pp. 627–632, November, 1973.     

Linearity of grid minors in treewidth with applications through bidimensionality

We prove that any H-minor-free graph, for a fixed graph H, of treewidth w has an Ω(w) × Ω(w) grid graph as a minor. Thus grid minors suffice to certify that H-minorfree graphs have large treewidth, up to constant factors. This strong relationship was previously known for the special cases of planar graphs and bounded-genus graphs, and is known not to hold for general graphs. The approach of this paper can be viewed more generally as a framework for extending combinatorial results on planar graphs to hold on H-minor-free graphs for any fixed H. Our result has many combinatorial consequences on bidimensionality theory, parameter-treewidth bounds, separator theorems, and bounded local treewidth; each of these combinatorial results has several algorithmic consequences including subexponential fixed-parameter algorithms and approximation algorithms. A preliminary version of this paper appeared in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2005) [16].     

Rotations: Matching schemes that efficiently preserve the best reply structure of a one shot game

Suppose that we have a two player game in which we want to test experimentally whether the subjects learn to play the game theoretic solution. For this purpose we need a matching scheme which assures that a rational subject behaves in each round of the experiment as if he played a separate stage game. In this paper we show that such a ‘best-reply-structure-preserving matching scheme’ has to be free of repercussion effects, and that the rotation of two equally sized groups of subjects, which was introduced by Cooper, DeJong, Forsythe and Ross, solves the problem efficiently.     

The similarity between the best approximation and the best copositive approximation

In this paper the author studies the copositive approximation in C(?) by elements of finite dimensional Chebyshev subspaces in the general case when ? is any totally ordered compact space. He studies the similarity between me behavior of the ordinary best approximation and the behavior pf the copositive best approximation. At the end of this paper, the author isolates many cases at which the two behaviors are the same.     

An ABS algorithm for solving singular nonlinear systems with rank one defect

A modified discretization ABS algorithm for solving a class of singular nonlinear systems, F(x) = 0, wherex, F ∈ Rⁿ, is presented, constructed by combining a discretization ABS algorithm and a method of Hoy and Schwetlick (1990). The second order differential operation ofF at a point is not required to be calculated directly in this algorithm. Q-quadratic convergence of this algorithm is given.     

An algorithm for best approximate solutions ofAx=b with a smooth strictly convex norm

Summary In this paper, overdetermined systems ofm linear equations inn unknowns are considered. With ^m equipped with a smooth strictly convex norm, ·, an iterative algorithm for finding the best approximate solution of the linear system which minimizes the ·-error is given. The convergence of the algorithm is established and numerical results are presented for the case when · is anl _p norm, 1<p<.Portions of this paper are taken from the author's Ph.D. thesis at Michigan State University     

A problem in enumerating extreme points, and an efficient algorithm for one class of polytopes

We consider the problem of developing an efficient algorithm for enumerating the extreme points of a convex polytope specified by linear constraints. Murty and Chung (Math Program 70:27–45, 1995) introduced the concept of a segment of a polytope, and used it to develop some steps for carrying out the enumeration efficiently until the convex hull of the set of known extreme points becomes a segment. That effort stops with a segment, other steps outlined in Murty and Chung (Math Program 70:27–45, 1995) for carrying out the enumeration after reaching a segment, or for checking whether the segment is equal to the original polytope, do not constitute an efficient algorithm. Here we describe the central problem in carrying out the enumeration efficiently after reaching a segment. We then discuss two procedures for enumerating extreme points, the mukkadvayam checking procedure, and the nearest point procedure. We divide polytopes into two classes: Class 1 polytopes have at least one extreme point satisfying the property that there is a hyperplane H through that extreme point such that every facet of the polytope incident at that extreme point has relative interior point intersections with both sides of H; Class 2 polytopes have the property that every hyperplane through any extreme point has at least one facet incident at that extreme point completely contained on one of its sides. We then prove that the procedures developed solve the problem efficiently when the polytope belongs to Class 2.     

The Lascoux, Leclerc and Thibon algorithm and Soergel's tilting algorithm

We generalize Soergel's tilting algorithm to singular weights and deduce from this the validity of the Lascoux-Leclerc-Thibon conjecture on the connection between the canonical basis of the basic submodule of the Fock module and the representation theory of the Hecke-algebras at root of unity. Supported in part by Programa Reticulados y Ecuaciones and by FONDECYT grant 1051024.