A Further Improved Approximation Algorithm for Breakpoint Graph Decomposition

Breakpoint graph decomposition is a crucial step in all recent approximation algorithms for SORTING BY REVERSALS, which is one of the best-known algorithmic problems in computational molecular biology. Caprara and Rizzi recently improved the approximation ratio for breakpoint graph decomposition from to + 1.4348 + , for any positive . In this paper, we extend the techniques of Caprara and Rizzi and incorporate a balancing argument to further improve the approximation ratio to + 1.4193 + , for any positive . These improvements imply improved approximation results for SORTING BY REVERSALS for almost all random permutations.     

正式函数程序设计语言FFP在微机上的实现

本文描述了在M68000 DUAL系统上用C语言实现的正式函数程序设计语言FFP-1,从而在微机上证明了FFP-1系统的可行性。由于FFP语言是作用式、归约式的语言,因此采用了图归约机和延迟求值技术。     

用图论原理进行工艺过程的尺寸分析与线性工艺尺寸的确定

在机械加工中，被加工对象可看成是由多个表面和表面间的联系所构成的几何结构．对较复杂的工艺过程，用图论原理去分析、研究和求解工艺尺寸链，较之常规方法显得更为方便、简单和准确．     

Necessary Edges in k-Chordalisations of Graphs

A k-chordalisation of a graph G = (V,E) is a graph H = (V,F) obtained by adding edges to G, such that H is a chordal graph with maximum clique size at most k. This note considers the problem: given a graph G = (V,E) which pairs of vertices, non-adjacent in G, will be an edge in every k-chordalisation of G. Such a pair is called necessary for treewidth k. An equivalent formulation is: which edges can one add to a graph G such that every tree decomposition of G of width at most k is also a tree decomposition of the resulting graph G. Some sufficient, and some necessary and sufficient conditions are given for pairs of vertices to be necessary for treewidth k. For a fixed k, one can find in linear time for a given graph G the set of all necessary pairs for treewidth k. If k is given as part of the input, then this problem is coNP-hard. A few similar results are given when interval graphs (and hence pathwidth) are used instead of chordal graphs and treewidth.     

An Edge-Splitting Algorithm in Planar Graphs

For a multigraph G = (V, E), let s V be a designated vertex which has an even degree, and let _G (V – s) denote min{c _G(X) | Ø X V – s}, where c _G(X) denotes the size of cut X. Splitting two adjacent edges (s, u) and (s, v) means deleting these edges and adding a new edge (u, v). For an integer k, splitting two edges e ₁ and e ₂ incident to s is called (k, s)-feasible if _G(V – s) k holds in the resulting graph G. In this paper, we prove that, for a planar graph G and an even k or k = 3 with k _G (V – s), there exists a complete (k, s)-feasible splitting at s such that the resulting graph G is still planar, and present an O(n ³ log n) time algorithm for finding such a splitting, where n = |V|. However, for every odd k 5, there is a planar graph G with a vertex s which has no complete (k, s)-feasible and planarity-preserving splitting. As an application of this result, we show that for an outerplanar graph G and an even integer k the problem of optimally augmenting G to a k-edge-connected planar graph can be solved in O(n ³ log n) time.     

高可靠准随机网络的结构

研究了以下网络可靠性综合问题:对给定的p和q,以及边失效率(或点失效率)p,构造具有p个点和q条边的图,使其在仅考虑边失效率(或点失效率)为p时,所成网络的可靠性最高。特别讨论了p=1/2的情况。     

非H-无爪图最长圈的若干性质

设G是2-连通无爪图,C是G的最长圈,R=G-C非空.证明了C满足以下5个性质;1)不存在c∈Nc(R),使G[N(c)]连通;2)不存在c∈Nc(R)和y∈V(G)(y≠c),使G[N(c)U{y}]连通且|N(y)∩N(c)|≥3;3)不存在c∈Nc(R)和y∈V(G),使G[N(c)∪{y}连通且G[N(y)]连通;4)不存在c∈Nc(R)和y∈K_1,使|N(y)∩(N(K_2)-{c}|≥2(其中K_1是G[N(c)]的含c~+,c~-的一个分支,K_2是另一个分支);5)不存在c∈Nc(R)和y∈V(G),使|N(y)∩K_1|≥2且有连接K_2与y的路P满足:对P的任一中途点u,或u∈V(C)或u~+u~-∈E(G).     

3-连通无爪图中的最长圈

证明了3-连通无爪图G中的最长圈C满足:|V(C)|≥min{3δ(G)+6,5δ(G)-5,4δ(G),|V(G)|}.     

Maximum cyclic 4-cycle packings of the complete multipartite graph

A graph G is said to be m-sufficient if m is not exceeding the order of G, each vertex of G is of even degree, and the number of edges in G is a multiple of m. A complete multipartite graph is balanced if each of its partite sets has the same size. In this paper it is proved that the complete multipartite graph G can be decomposed into 4-cycles cyclically if and only if G is balanced and 4-sufficient. Moreover, the problem of finding a maximum cyclic packing of the complete multipartite graph with 4-cycles are also presented. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.     

Characterizing the reconstruction and enumerating the patterns of DNA sequences with repeats

A repeat in a DNA sequence is a substring that appears more than once. In DNA sequencing, the occurrence of repeats may hinder the unique reconstruction. In addition, the number of possible reconstructions depends on the pattern of repeats in a DNA sequence. Arratia et al. studied the patterns of DNA sequences with twofold repeats that result in k-way reconstructions. In this paper, multiple-fold repeats, including twofold repeats, are considered. For each pattern of DNA repeats, the possible reconstructions of the DNA sequence are enumerated by its reduced digraph. Then the reconstructions of DNA sequences with repeats are characterized using the pattern graphs. Finally, for DNA sequences with n repeats, the patterns of DNA repeats resulting in k-way reconstruction are enumerated. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.