A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph

We present a simple unified algorithmic process which uses either LexBFS or MCS on a chordal graph to generate the minimal separators and the maximal cliques in linear time in a single pass.     

A Fully Dynamic Graph Algorithm for Recognizing Interval Graphs

We present the first dynamic graph algorithm for recognizing interval graphs. The algorithm runs in O(nlog?n) worst-case time per edge deletion or edge insertion, where n is the number of vertices in the graph. The algorithm uses a new representation of interval graphs called the train tree, which is based on the clique-separator graph representation of chordal graphs. The train tree has a number of useful properties and it can be constructed from the clique-separator graph in O(n) time.     

Minimal covering problem and PLA minimization

Solving the minimal covering problem by an implicit enumeration method is discussed. The implicit enumeration method in this paper is a modification of the Quine-McCluskey method tailored to computer processing and also its extension, utilizing some new properties of the minimal covering problem for speedup. A heuristic algorithm is also presented to solve large-scale problems. Its application to the minimization of programmable logic arrays (i.e., PLAs) is shown as an example. Computational experiences are presented to confirm the improvements by the implicit enumeration method discussed.This work was supported in part by the National Science Foundation under Grants Nos. MCS77-09744 and MCS81-08505 and also by the Department of Computer Science.M.-H. Young was with the Department of Computer Science, University of Illinois, Urbana, Illinois.     

Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions

We study graph properties that admit an increasing, or equivalently decreasing, sequence of graphs on the same vertex set such that for any two consecutive graphs in the sequence their difference is a single edge. This is useful for characterizing and computing minimal completions and deletions of arbitrary graphs into having these properties. We prove that threshold graphs and chain graphs admit such sequences. Based on this characterization and other structural properties, we present linear-time algorithms both for computing minimal completions and deletions into threshold, chain, and bipartite graphs, and for extracting a minimal completion or deletion from a given completion or deletion. Minimum completions and deletions into these classes are NP-hard to compute.     

A good characterization of squares of strongly chordal split graphs

The square H² of a graph H is obtained from H by adding new edges between every two vertices having distance two in H. Lau and Corneil [Recognizing powers of proper interval, split and chordal graphs, SIAM J. Discrete Math. 18 (2004) 83-102] proved that recognizing squares of split graphs is an NP-complete problem. In contrast, we show that squares of strongly chordal split graphs can be recognized in quadratic-time by giving a structural characterization of these graph class.     

On listing,sampling, and counting the chordal graphs with edge constraints

We discuss the problems to list, sample, and count the chordal graphs with edge constraints. The objects we look at are chordal graphs sandwiched by a given pair of graphs where we assume that at least one of the input graphs is chordal. The setting is a natural generalization of chordal completions and deletions. For the listing problem, we give an efficient algorithm running in polynomial time per output with polynomial space. As for the sampling problem, we give two clues that indicate that a random sampling is not easy. The first clue is that we show #P-completeness results for counting problems. The second clue is that we give an instance for which a natural Markov chain suffers from an exponential mixing time. These results provide a unified viewpoint from algorithms’ theory to problems arising from various areas such as statistics, data mining, and numerical computation.     

Clustering based on multiple paths

This paper deals with a separation of strongly touching clusters using a concept of n-connectedness between pattern pairs, i.e., the number of paths between patterns. This new concept is similar to the concept of n-connectedness of graphs. Classification algorithms based on the number of independent paths and edge-disjoint paths are presented. It is shown that the latter has a transitivity. Finally, a simpler algorithm, i.e., a classification method based on the total number of paths, is presented. The proposed algorithm may be seen as an intermediate one between the ordinary connectedness algorithm and the maximal complete subgraph (MCS) algorithm.     

Generating and coding of fractal graphs by neural network andmathematical morphology methods

We present an algorithm for generating a class of self-similar (fractal) graphs using simple probabilistic logic neuron networks and show that the graphs can be represented by a set of compressed encoding. An algorithm for quickly finding the coding, i.e., recognizing the corresponding graphs, is given and the coding are shown to be optimal (i.e., of minimal length). The same graphs can also be generated by a mathematical morphology method. These results may possibly have applications in image compression and pattern recognition.     

一种基于神经网络的分形几何图的产生与编码

本文提出用概率逻辑神经网产生一类自（互）相似（分形）图的方法，指出这类图能用一组压缩编码表示，给出快速寻找该编码的算法，既识别该分形几何图的算法，证明该编码是最优的，即码的长度最短，这些成果有希望在图象压缩和模式识别中得到应用。     

Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs

The densest k-subgraph problem asks for a k-vertex subgraph with the maximum number of edges. This problem is NP-hard on bipartite graphs, chordal graphs, and planar graphs. A 3-approximation algorithm is known for chordal graphs. We present -approximation algorithms for proper interval graphs and bipartite permutation graphs. The latter result relies on a new characterisation of bipartite permutation graphs which may be of independent interest.     

k-tuple domination in graphs

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k vertices in this set. The current paper studies k-tuple domination in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the k-tuple domination problem in strongly chordal graphs, which is a subclass of chordal graphs and includes trees, block graphs, interval graphs and directed path graphs. We also prove that the k-tuple domination problem is NP-complete for split graphs (a subclass of chordal graphs) and for bipartite graphs.     

Generating and characterizing the perfect elimination orderings of a chordal graph

We develop a constant time transposition “oracle” for the set of perfect elimination orderings of chordal graphs. Using this oracle, we can generate a Gray code of all perfect elimination orderings in constant amortized time using known results about antimatroids. Using clique trees, we show how the initialization of the algorithm can be performed in linear time. We also develop two new characterizations of perfect elimination orderings: one in terms of chordless paths, and the other in terms of minimal u-v separators.     

Uniquely Restricted Matchings

A matching in a graph is a set of edges no two of which share a common vertex. In this paper we introduce a new, specialized type of matching which we call uniquely restricted matchings, originally motivated by the problem of determining a lower bound on the rank of a matrix having a specified zero/ non-zero pattern. A uniquely restricted matching is defined to be a matching M whose saturated vertices induce a subgraph which has only one perfect matching, namely M itself. We introduce the two problems of recognizing a uniquely restricted matching and of finding a maximum uniquely restricted matching in a given graph, and present algorithms and complexity results for certain special classes of graphs. We demonstrate that testing whether a given matching M is uniquely restricted can be done in O(|M||E|) time for an arbitrary graph G=(V,E) and in linear time for cacti, interval graphs, bipartite graphs, split graphs and threshold graphs. The maximum uniquely restricted matching problem is shown to be NP-complete for bipartite graphs, split graphs, and hence for chordal graphs and comparability graphs, but can be solved in linear time for threshold graphs, proper interval graphs, cacti and block graphs. Received April 12, 1998; revised June 21, 1999.     

基于等价关系的最小乐观概念格生成算法

决策信息系统的规则提取是数据挖掘的研究内容之一,概念格理论与粒计算理论是该领域研究的主要数学工具.文中通过探究这两大理论间的关系,利用等价关系定义了最小乐观概念格及其结构,最小乐观概念区别于传统经典概念,但是具有格的结构.在此基础上,提出了一种决策信息系统的规则提取算法,该算法引入了粒度思想,通过求取每一粒层中的最小乐...     

Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

A spanning tree T of a graph G=(V,E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G for all v∈V. The problem of recognizing whether a graph admits a locally connected spanning tree is known to be NP-complete even when the input graphs are restricted to chordal graphs. In this paper, we propose linear time algorithms for finding locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, respectively.     

Maximum Induced Matchings for Chordal Graphs in Linear Time

The Maximum Induced Matching (MIM) Problem asks for a largest set of pairwise vertex-disjoint edges in a graph which are pairwise of distance at least two. It is well-known that the MIM problem is NP-complete even on particular bipartite graphs and on line graphs. On the other hand, it is solvable in polynomial time for various classes of graphs (such as chordal, weakly chordal, interval, circular-arc graphs and others) since the MIM problem on graph G corresponds to the Maximum Independent Set problem on the square G ^*=L(G)² of the line graph L(G) of G, and in some cases, G ^* is in the same graph class; for example, for chordal graphs G, G ^* is chordal. The construction of G ^*, however, requires time, where m is the number of edges in G. Is has been an open problem whether there is a linear-time algorithm for the MIM problem on chordal graphs. We give such an algorithm which is based on perfect elimination order and LexBFS.     

A constant approximation algorithm for the densest k-subgraph problem on chordal graphs

The densest k-subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The DkS problem is NP-hard even for special graph classes including bipartite, planar, comparability and chordal graphs, while no constant approximation algorithm is known for any of these classes. In this paper we present a 3-approximation algorithm for the class of chordal graphs. The analysis of our algorithm is based on a graph theoretic lemma of independent interest.     

基于不可满足原因的最小纠正集求解

布尔公式的最小纠正集MCS是子句的集合。对于一个不可满足公式,移除MCS后,所得到的新公式可满足。任一MCS中的子句保留在公式中,所得到的新公式不可满足。通过求解MCS 并调整约束集合,能够求解最小不可满足核心、MaxSAT 问题和最大（小）可满足解问题;还能够应用于故障定位、模型检查配置优化等实际问题中。 提出了一种基于不可满足原因的MCS求解算法,实现了相应的CUC工具。通过与目前最好的MCS求解工具LBX进行比较,得到了CUC性能优于LBX的结论。CUC比LBX平均多解出5%（65个）的公式。对于CUC和LBX均可解出的公式,CUC的平均求解时间比LBX快2.5倍。     

On Independent Vertex Sets in Subclasses of Apple-Free Graphs

In a finite undirected graph, an apple consists of a chordless cycle of length at least 4, and an additional vertex which is not in the cycle and sees exactly one of the cycle vertices. A graph is apple-free if it contains no induced subgraph isomorphic to an apple. Apple-free graphs are a common generalization of chordal graphs, claw-free graphs and cographs and occur in various papers. The Maximum Weight Independent Set (MWS) problem is efficiently solvable on chordal graphs, on cographs as well as on claw-free graphs. In this paper, we obtain partial results on some subclasses of apple-free graphs where our results show that the MWS problem is solvable in polynomial time. The main tool is a combination of clique separators with modular decomposition. Our algorithms are robust in the sense that there is no need to recognize whether the input graph is in the given graph class; the algorithm either solves the MWS problem correctly or detects that the input graph is not in the given class.     

Tree spanners on chordal graphs: complexity and algorithms

A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The T t-S problem asks whether a graph admits a tree t-spanner, given t. We substantially strengthen the hardness result of Cai and Corneil (SIAM J. Discrete Math. 8 (1995) 359–387) by showing that, for any t4, T t-S is NP-complete even on chordal graphs of diameter at most t+1 (if t is even), respectively, at most t+2 (if t is odd). Then we point out that every chordal graph of diameter at most t−1 (respectively, t−2) admits a tree t-spanner whenever t2 is even (respectively, t3 is odd), and such a tree spanner can be constructed in linear time.

The complexity status of T 3-S still remains open for chordal graphs, even on the subclass of undirected path graphs that are strongly chordal as well. For other important subclasses of chordal graphs, such as very strongly chordal graphs (containing all interval graphs), 1-split graphs (containing all split graphs) and chordal graphs of diameter at most 2, we are able to decide T 3-S efficiently.