Lower bounds on the pathwidth of some grid-like graphs

We present proofs of lower bounds on the node search number of some grid-like graphs including two-dimensional grids, cylinders, tori and a variation we call “orb-webs”. Node search number is equivalent to pathwidth and vertex separation, which are all important graph parameters. Since matching upper bounds are not difficult to obtain, this implies that the pathwidth of these graphs is easily computed, because the bounds are simple functions of the graph dimensions. We also show matching upper and lower bounds on the node search number of equidimensional tori which are one less than the obvious upper bound.     

Pathwidth of outerplanar graphs

We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant c such that the pathwidth of every biconnected outerplanar graph is at most c plus the pathwidth of its dual. They also conjectured that this was actually true with c being one for every biconnected planar graph. Fomin [10] proved that the second conjecture is true for all planar triangulations. First, we construct for each p ≥ 1, a biconnected outerplanar graph of pathwidth 2p + 1 whose (geometric) dual has pathwidth p + 1, thereby disproving both conjectures. Next, we also disprove two other conjectures (one of Bodlaender and Fomin [3], implied by one of Fomin [10]. Finally we prove, in an algorithmic way, that the pathwidth of every biconnected outerplanar graph is at most twice the pathwidth of its (geometric) dual minus one. A tight interval for the studied relation is therefore obtained, and we show that all cases in the interval happen. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 27–41, 2007     

图的扩张与稀疏矩阵计算中的若干优化问题

本文研究从稀疏矩阵计算中提出的若干离散最优化问题,即带宽,树宽,路宽,侧廓,扩充侧廓及填充问题。实际上,它们是一类图扩张问题;这些问题同时来源于各式各样的课题,如图子式理论,VLSI电路设计,互联网络及分子生物学等,本文从图论观点着重讨论两种统一途径：图的标号及图的扩张。     

Approximation of pathwidth of outerplanar graphs

There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs, but the large exponent makes this algorithm impractical. In this paper, we give an algorithm that, given a biconnected outerplanar graph G, finds a path decomposition of G of pathwidth at most twice the pathwidth of G plus one. To obtain the result, several relations between the pathwidth of a biconnected outerplanar graph and its dual are established.     

树的补图的区间图完全化问题

一个图G的区间图完全化问题包含两类子问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G),其中侧廓问题是寻求G的一个边数最小的区间超图;路宽问题是寻求G的一个团数最小的区间超图.这两类子问题分别在数值代数、VLSI-设计和算法图论等学科领域中有重要的应用.对一般图来说,两类子问题都是NP-完全问题;但是对一些特殊图类来说,它们在多项式时间内可解.本文给出了树T的补图的具体侧廓和路宽值.     

On self duality of pathwidth in polyhedral graph embeddings

Let G be a 3‐connected planar graph and G^* be its dual. We show that the pathwidth of G^* is at most 6 times the pathwidth of G. We prove this result by relating the pathwidth of a graph with the cut‐width of its medial graph and we extend it to bounded genus embeddings. We also show that there exist 3‐connected planar graphs such that the pathwidth of such a graph is at least 1.5 times the pathwidth of its dual. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 42–54, 2007     

Lattice bandwidth of random graphs

The bandwidth of a random graph has been well studied. A natural generalization of bandwidth involves replacing the path as host graph by a multi-dimensional lattice. In this paper we investigate the corresponding behavior for random graphs.     

完全多部图的区间图完全化问题

The interval graph completion problem of a graph G includes two class problems: the profile problem and the pathwidth problem, denoted as P(G) and PW(G) respectively, where the profile problem is to find an interval supergraph with the smallest possible number of edges; the pathwidth problem is to find an interval supergraph with the smallest possible cliquesize. These two class problems have important applications to numerical algebra, VLSI-layout and algorithm graph theory respectively; And they are known to be NP-complete for general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the exact solutions of the profile and the pathwidth of the complete multipartite Graph Kn1,n2,…,nr(r≥2) are determined.     

QoS-Guided Bandwidth Management in Differentiated Time Scales

This paper presents an integrated approach to QoS-guided network bandwidth allocation where each traffic flow requires a sufficient bandwidth allocation to support its mean traffic rate and to meet a delay requirement. Under the assumption that the peak rate of each traffic flow is decreasing with the time interval within which the rate is measured, we derive an analytical relationship between the delay bound and the bandwidth requirement for each individual flow. Then, based on a Gaussian aggregate traffic model, we show that two key controllable parameters, the coefficient of variation and the provision for variation for the aggregate traffic flow, determine all three fundamental QoS attributes (throughput, delay, and loss). We illustrate by examples that these results can be used to design admission policies. We demonstrate also quantitatively a remarkable QoS advantage of larger channel bandwidth in a statistical multiplexing environment. The analytical contributions are expected to be generally useful in QoS-guided bandwidth management in broadband networks.     

Local Fourier Analysis of Multigrid Methods with Polynomial Smoothers and Aggressive Coarsening

We focus on the study of multigrid methods with aggressive coarsening and polynomial smoothers for the solution of the linear systems corresponding to finite difference/element discretizations of the Laplace equation. Using local Fourier analysis we determine automatically the optimal values for the parameters involved in defining the polynomial smoothers and achieve fast convergence of cycles with aggressive coarsening. We also present numerical tests supporting the theoretical results and the heuristic ideas. The methods we introduce are highly parallelizable and efficient multigrid algorithms on structured and semi-structured grids in two and three spatial dimensions.     

图的消去割宽问题

图搜索问题在组合最优化学科中是一个著名的NP-完全问题.现在我们给这个问题一个限制性条件：图中的边在一次性被搜索后立即堵塞,使得这些边在以后的图搜索过程中不再被搜索.该问题起源于流行病的预防、管道的保养和维护等领域. 在这个条件限制下,图搜索问题可以转化为图的消去割宽问题.本文主要研究了图的消去割宽的多项式时间算法、基本性质以及消去割宽和其它图论参数如树宽、路宽的关系,得到了一些特殊图类的消去割宽值.     

Edge searching weighted graphs

In traditional edge searching one tries to clean all of the edges in a graph employing the least number of searchers. It is assumed that each edge of the graph initially has a weight equal to one. In this paper we modify the problem and introduce the Weighted Edge Searching Problem by considering graphs with arbitrary positive integer weights assigned to its edges. We give bounds on the weighted search number in terms of related graph parameters including pathwidth. We characterize the graphs for which two searchers are sufficient to clear all edges. We show that for every weighted graph the minimum number of searchers needed for a not-necessarily-monotonic weighted edge search strategy is enough for a monotonic weighted edge search strategy, where each edge is cleaned only once. This result proves the NP-completeness of the problem.     

Ramsey numbers for bipartite graphs with small bandwidth

We estimate Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. In particular we determine asymptotically the two and three color Ramsey numbers for grid graphs. More generally, we determine asymptotically the two color Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that the bipartite graph is balanced.     

The stable set problem and the thinness of a graph

We introduce a poly-time algorithm for the maximum weighted stable set problem, when a certain representation is given for a graph. The algorithm generalizes the algorithm for interval graphs and that for graphs with bounded pathwidth. By a suitable application to the frequency assignment problem, we improved several solutions to relevant benchmark instances.     

A variable step-size control algorithm for the weak approximation of stochastic differential equations

In this paper, we propose two local error estimates based on drift and diffusion terms of the stochastic differential equations in order to determine the optimal step-size for the next stage in an adaptive variable step-size algorithm. These local error estimates are based on the weak approximation solution of stochastic differential equations with one-dimensional and multi-dimensional Wiener processes. Numerical experiments are presented to illustrate the effectiveness of this approach in the weak approximation of several standard test problems including SDEs with small noise and scalar and multi-dimensional Wiener processes.     

A 3-approximation for the pathwidth of Halin graphs

We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.     

Forbidden minors to graphs with small feedback sets

Finite obstruction set characterizations for lower ideals in the minor order are guaranteed to exist by the graph minor theorem. In this paper we characterize several families of graphs with small feedback sets, namely k₁-F V S , k₂-F E S and (k₁,k₂)-F V /E S , for small integer parameters k₁ and k₂. Our constructive methods can compute obstruction sets for any minor-closed family of graphs, provided the pathwidth (or treewidth) of the largest obstruction is known.     

树的线图的图扩充问题

图G的弦图扩充问题包含两个问题:图G的最小填充问题和树宽问题,分别表示为f(G)和TW(G);图G的区间图扩充问题也包含两个问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G).对一般图而言,它们都是NP-困难问题.一些特殊图类的填充数、树宽、侧廓问题和路宽具体值已被求出.主要研究树T的线图L(T)的弦图扩充问题;其次涉及到了两类特殊树—毛虫树和直径为4的树的线图的区间图扩充问题.     

Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs

In this paper, it is shown that the maximum pagenumber of the graphs with pathwidth k is k and that the maximum pagenumber of the graphs with strong pathwidth k is in between ⌈3(k−1)/2⌉ and 3⌈k/2⌉.     

Fluid models of integrated traffic and multipath routing

In this paper we consider a stochastic model describing the varying number of flows in a network. This model features flows of two types, namely file transfers (with fixed volume) and streaming traffic (with fixed duration), and extends the model of Key, Massoulié, Bain and Kelly [27] by allowing more general bandwidth allocation criteria. We analyse the dynamics of the system under a fluid scaling, and show Lyapunov stability of the fluid limits under a natural stability condition. We provide natural interpretations of the fixed points of these fluid limits. We then compare the fluid dynamics of file transfers under (i) balanced multipath routing and (ii) parallel, uncoordinated routing. We show that for identical traffic demands, parallel uncoordinated routing can be unstable while balanced multipath routing is stable. Finally, we identify multi-dimensional Ornstein-Uhlenbeck processes as second-order approximations to the first-order fluid limit dynamics.