The Longest Path Problem Is Polynomial on Cocomparability Graphs

The longest path problem is the problem of finding a path of maximum length in a graph. As a generalization of the Hamiltonian path problem, it is NP-complete on general graphs and, in fact, on every class of graphs that the Hamiltonian path problem is NP-complete. Polynomial solutions for the longest path problem have recently been proposed for weighted trees, Ptolemaic graphs, bipartite permutation graphs, interval graphs, and some small classes of graphs. Although the Hamiltonian path problem on cocomparability graphs was proved to be polynomial almost two decades ago, the complexity status of the longest path problem on cocomparability graphs has remained open; actually, the complexity status of the problem has remained open even on the smaller class of permutation graphs. In this paper, we present a polynomial-time algorithm for solving the longest path problem on the class of cocomparability graphs. Our result resolves the open question for the complexity of the problem on such graphs, and since cocomparability graphs form a superclass of both interval and permutation graphs, extends the polynomial solution of the longest path problem on interval graphs and provides polynomial solution to the class of permutation graphs.     

An Interval Polynomial Interpolation Problem and Its Lagrange Solution

In many practical problems, we need to use interpolation: we know that the value of a quantity is uniquely determined by some other quantity x (i.e., y = f(x)), we have measured several pairs of values (xi, yi), and we want to predict y for a given x. We can only guarantee estimates for y if we have some a priori information about the function f(x). In particular, in some problems, we know that f(x) is a polynomial of known degree d (e.g., that it is linear, or that it is quadratic). For this polynomial interpolation, with interval uncertainty of the input data (xi, yi), we present several reasonable algorithms that compute, for a given x0, guaranteed bounds for f(x0).     

On the Sum Coloring Problem on Interval Graphs

In this paper we study the following NP-complete problem: given an interval graph G = (V,E) , find a node p -coloring such that the cost is minimal, where denotes a partition of V whose subsets are ordered by nonincreasing cardinality. We present an O(m χ (G) + n log n) time ε -approximate algorithm (ε < 2) to solve the problem, where n , m , and χ #(G) are the number of nodes of the interval graph, its number of cliques, and its chromatic number, respectively. The algorithm is shown to solve the problem exactly on some classes of interval graphs, namely, the proper and the containment interval graphs, and the intersection graphs of sets of ``short' intervals. The problem of determining the minimum number of colors needed to achieve the minimum over all p -colorings of G is also addressed. Received February 1, 1996; revised August 22, 1997.     

The Steiner Problem in Graphs: Topological Methods of Solution

Algorithms for the Steiner problem and its generalizations on large graphs with a relatively small number of terminal vertices are designed by a two-level solution scheme: a network topology (i.e., a tree determining the adjacency of terminal vertices and branching points) is determined in the upper level and the optimal location for branching points with the topology found in the upper level is determined in the lower level.     

求解区间图K-连接最短路径问题的在线算法

针对含有n个区间的区间图K-连接最短路径(K-SP)问题,提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质,利用改进的动态规划算法和贪心算法,优化在线算法的时间复杂度。理论分析结果表明,该算法的时间复杂度为O(nK+nlgn),与目前已知最优的离线算法复杂度相同。     

Excel求解最短路径问题

许多实际应用问题都与最短路径相关,解决最短路径问题通常采用图论与计算机技术结合的方法,使用Excel的工作表和自定义宏函数,采用Dijkstra算法和链表动态数据结构解决最短路径问题,并在Excel的VBA环境编程运行。     

网树求解有向无环图中具有长度约束的简单路径和最长路径问题

具有长度约束的简单路径(Simple Paths with Length Constraint,SPLC)问题是指求解图中任意两点间路径长度为m的简单路径数,是k-path问题的一种特殊情况.该文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs,NSPLCDAG).网树是一种多树根多双亲的数据结构.NSPLCDAG算法将该问题转化为一棵网树后,利用树根路径数这一性质对其进行求解.对NSPLCDAG算法进行改造,可以求解有向无环图中最长路径问题并形成网树求解最长路径算法(Nettree for the Longest Path in DAGs,NLPDAG),NLPDAG算法可找到所有最长路径,对NLPDAG算法做进一步改进形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径.实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性.     

Polynomial Solution to Stabilization Problem for Multivariable Sampled-Data Systems

In polynomial form, necessary and sufficient conditions are given that provide for existence of a discrete controller stabilizing a multivariable sampled-data system.     

Sharp Bounds on Interval Polynomial Roots

An algorithm is developed for computing sharp bounds on the real roots of polynomials with interval coefficients. The procedure is introduced by studying interval quadratic equations.     

最长递增子序列问题研究

本文采用分治策略和动态规划策略探讨了最长递增子序列问题的两种解法,并分析了算法的计算复杂度。结果表明,本文算法的时间复杂度和空间复杂度分别为O(nlogn)和O(n)。     

最短路径问题及其解法研究

最短路径问题是在给定的网络图中寻找出一务从起始点到目标点之间的最短路径。该文分别从动态规划、Dijkstra、A＊算法、遗传算法这四种算法设计方法入手,概述了各种设计方法的原理,提出了求解最短路径的算法思想,并对算法进行分析．提出了改进方法。     

基于分布式约束满足的多约束单路径路由问题求解

约束路由问题是IP网络的一个核心功能,由于求解多约束路由问题属于NP完全问题,所以大量的研究工作围绕此展开.基于分布式约束满足的思想,设计多约束单路径路由问题求解算法,分析表明该求解算法降低计算复杂度,提高算法的性能.在分布式条件下完成算法的实现,经实验表明,算法近似程度较好,求解速度快.     

An Approximate Solution of a Variational Problem by the Shortest Path Method

A special graph is used to construct a difference scheme approximating a variational problem. The difference scheme is solved by an algorithm for determining the shortest path (path of minimal weight) on the graph. This solution is taken to be the approximate solution of the variational problem.     

区间多项式Schur稳定的一个结果

本文证明了ｎ次区间多项式Ｓｃｈｕｒ稳定的充分条件是２＾ｎ个多项式皆Ｓｃｈｕｒ稳定，并进一步给出了一种能逼近区间多项式Ｓｃｈｕｒ稳定充要条件的判别方法。     

The k-in-a-Path Problem for Claw-free Graphs

The k-in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbitrary fixed integer not part of the input. As a consequence, also the k-Induced Disjoint Paths and the k-in-a-Cycle problem are solvable in polynomial time on claw-free graphs for any fixed k. The first problem has as input a graph G and k pairs of specified vertices (s _i ,t _i ) for i=1,…,k and is to test whether G contain k mutually induced paths P _i such that P _i connects s _i and t _i for i=1,…,k. The second problem is to test whether a graph contains an induced cycle spanning k given vertices. When k is part of the input, we show that all three problems are NP-complete, even for the class of line graphs, which form a subclass of the class of claw-free graphs.     

Scheduling with Conflicts on Bipartite and Interval Graphs

In this paper, we consider the on-line scheduling of jobs that may be competing for mutually exclusive resources. We model the conflicts between jobs with a conflict graph, so that the set of all concurrently running jobs must form an independent set in the graph. This model is natural and general enough to have applications in a variety of settings; however, we are motivated by the following two specific applications: traffic intersection control and session scheduling in high speed local area networks with spatial reuse. Our results focus on two special classes of graphs motivated by our applications: bipartite graphs and interval graphs. The cost function we use is maximum response time. In all of the upper bounds, we devise algorithms which maintain a set of invariants which bound the accumulation of jobs on cliques (in the case of bipartite graphs, edges) in the graph. The lower bounds show that the invariants maintained by the algorithms are tight to within a constant factor. For a specific graph which arises in the traffic intersection control problem, we show a simple algorithm which achieves the optimal competitive ratio.     

Outer Interval Solution of the Eigenvalue Problem under General Form Parametric Dependencies

The paper addresses the problem of determining an outer interval solution of the parametric eigenvalue problem A(p)x = λx, A(p) ∈ ℝ^n×n for the general case where the matrix elements a_ij(p) are continuous nonlinear functions of the parameter vector p, p belonging to the interval vector p. A method for computing an interval enclosure of each eigenpair (λ_μ, x^(μ)), μ = 1, ..., n, is suggested for the case where λ_μ is a simple eigenvalue. It is based on the use of an affine interval approximation of a_ij(p) in p and reduces, essentially, to setting up and solving a real system of n or 2n incomplete quadratic equations for each real or complex eigenvalue, respectively.     

区间非线性路径约束的动态优化问题求解

本文研究路径约束中含有区间参数形式的动态优化问题,提出了一种新的非线性路径约束的确定化描述形式,和采用惩罚函数法的求解算法。对于转化后的极大极小优化命题,论文提出采用Lagrangian多项式加权和的方法得到有限维的确定性优化求解形式。该算法可有效地描述和求解不确定参数动态优化问题。