Maximum weight independent set in trees

Computing a maximum independent set, weighted or unweighted, isNP-hard for general as well as planar graphs. However, polynomial time algorithms do exist for solving this problem on special classes of graphs. In this paper we present an efficient algorithm for computing a maximum weight independent set in trees. A divide and conquer approach based on centroid decomposition of trees is used to compute a maximum weight independent set withinO(n logn) time, wheren is the number of vertices in the tree. We introduce a notion of analternating tree which is crucial in obtaining a new independent set from the previous one.     

Genetic algorithmic approach to find the maximum weight independent set of a graph

In this paper, Genetic Algorithm (GA) is used to find the Maximum Weight Independent Set (MWIS) of a graph. First, MWIS problem is formulated as a 0-1 integer programming optimization problem with linear objective function and a single quadratic constraint. Then GA is implemented with the help of this formulation. Since GA is a heuristic search method, exact solution is not reached in every run. Though the suboptimal solution obtained is very near to the exact one. Computational result comprising an average performance is also presented here.     

A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which is equivalent to the maximum matching problem in general graphs, has been proposed by Edmonds in 1965 and then extended to the entire class of claw-free graphs by Minty in 1980. Recently, Alekseev proposed a solution for the larger class of fork-free graphs, but only for the unweighted version of the problem, i.e., finding an independent set of maximum cardinality. In the present paper, we describe the first polynomial-time algorithm to solve the problem for weighted fork-free graphs.     

Partition the vertices of a graph into one independent set and one acyclic set

For a given graph G, if the vertices of G can be partitioned into an independent set and an acyclic set, then we call G a near-bipartite graph. This paper studies the recognition of near-bipartite graphs. We give simple characterizations for those near-bipartite graphs having maximum degree at most 3 and those having diameter 2. We also show that the recognition of near-bipartite graphs is NP-complete even for graphs where the maximum degree is 4 or where the diameter is 4.     

Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in $O\left(n^3\right)$-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in $O\left(n^4\right)$-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs.     

Finding a minimum independent dominating set in a permutation graph

We give a linear time reduction of the problem of finding a minimum independent dominating set in a permutation graph, into that of finding a shortest maximal increasing subsequence. We then give an O(n log²n)-time algorithm for solving the second (and hence the first) problem. This improves on the O(n³)-time algorithm given in [4] for solving the problem of finding a minimum independent dominating set in a permutation graph.     

Planar graph classes with the independent set problem solvable in polynomial time

The polynomial solvability of the independent set problem is proved for an infinite family of subsets of the class of planar graphs.     

Maximum generic nullity of a graph

For a graph G of order n, the maximum nullity of G is defined to be the largest possible nullity over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Maximum nullity and the related parameter minimum rank of the same set of matrices have been studied extensively. A new parameter, maximum generic nullity, is introduced. Maximum generic nullity provides insight into the structure of the null-space of a matrix realizing maximum nullity of a graph. It is shown that maximum generic nullity is bounded above by edge connectivity and below by vertex connectivity. Results on random graphs are used to show that as n goes to infinity almost all graphs have equal maximum generic nullity, vertex connectivity, edge connectivity, and minimum degree.     

The product of the independent domination numbers of a graph and its complement

It is shown that the maximum value over p vertex graphs of the product of the independent domination numbers of a graph and its complement is at most min {(p + 3)²/8, (p + 8)²/10.8}.     

Game,set, and graph

In the twentieth century the theory of games was transformed. It began as an amusing pastime, and ended as a major branch of mathematical research and a key paradigm of economic theory. Here it will be argued that the transformation was the result of the work of mathematicians, such as Ernst Zermelo, John von Neumann and Dénes K?nig, who also contributed to two other areas of mathematics that were emerging at the same time: the theory of sets and the theory of graphs.     

A hybrid iterated local search heuristic for the maximum weight independent set problem

This paper presents a hybrid iterated local search (ILS) algorithm for the maximum weight independent set (MWIS) problem, a generalization of the classical maximum independent set problem. Two efficient neighborhood structures are proposed and they are explored using the variable neighborhood descent procedure. Moreover, we devise a perturbation mechanism that dynamically adjusts the balance between intensification and diversification during the search. The proposed algorithm was tested on two well-known benchmarks (DIMACS-W and BHOSLIB-W) and the results obtained were compared with those found by state-of-the-art heuristics and exact methods. Our heuristic outperforms the best-known heuristic for the MWIS as well as the best heuristics for the maximum weight clique problem. The results also show that the hybrid ILS was capable of finding all known optimal solutions in milliseconds.     

An optimal time algorithm for finding a maximum weight independent set in a tree

The maximum weight independent set problem for a general graph is NP-hard. But for some special classes of graphs, polynomial time algorithms do exist for solving it. Based on the divide-and-conquer strategy, Pawagi has presented anO(|V|log|V|) time algorithm for solving this problem on a tree. In this paper, we propose anO(|V|) time algorithm to improve Pawagi's result. The proposed algorithm is based on the dynamic programming strategy and is time optimal within a constant factor.     

Weak set convergence and its application to projection methods

There are many examples in Numerical Analysis where convergence of approximate solutions to a solution of the original problem can not be shown in the sense of a norm topology but in the sense of weak convergence ([6], [9], [10]).

Moreover, (global) solutions are often not unique such that a concept of set convergence instead of convergence in the usual sense is more convenient and reasonable ([1], [2]). This particularly holds if weakly formulated problems are under consideration.

When dealing with problems where both situations coincide, a concept of weak set convergence seems to be adequate. Such a concept is developed and will be applied to certain projections methods.     

Fast algorithms for generating all maximal independent sets of interval,circular-arc and chordal graphs

In this paper we give fast algorithms for generating all maximal independent sets of three special classes of graphs—interval, circular-arc, and chordal graphs. The worst-case running times of our algorithms are O(n² + β) for interval and circular-arc graphs, and $\text{O((n + e)}{}^1\text{α)}$ for chordal graphs, where n, e, and α are the numbers of vertexes, edges, and maximal independent sets of a graph, and β is the sum of the numbers of vertexes of all maximal independent sets. Our algorithms compare favorably with the fastest known algorithm for general graphs which has a worst-case running time of $\text{O(n}{}^1\text{e}{}^1\text{α)}$.     

图映射的非游荡集

§ 1　IntroductionLet N be the set of all natural numbers.Write Z+=N∪ { 0 } ,Nn={ 1 ,2 ,...,n} andZn={ 0 }∪Nnfor any n∈N.Let X be a topological space and f:X→X be a continuous map.Forx∈X,O(x,f) ={ fk(x) :k∈ Z+} is called the orbit of x.The set of periodic points,the set of recurrentpoints,the set ofω-limit points for some x∈X and the set of non-wandering points of fare denoted by P(f) ,R(f) ,ω(x,f) andΩ(f) ,respectively(for the definitions see[1 ] ) .Let A X,we use int(A) ,A…     

The extreme set condition of a graph

Let G be a simple graph. The size of any largest matching in G is called the matching number of G and is denoted by ν(G). Define the deficiency of G, def(G), by the equation def(G)=|V(G)|−2ν(G). A set of points X in G is called an extreme set if def(G−X)=def(G)+|X|. Let c₀(G) denote the number of the odd components of G. A set of points X in G is called a barrier if c₀(G−X)=def(G)+|X|. In this paper, we obtain the following:

(1) Let G be a simple graph containing an independent set of size i, where i2. If X is extreme in G for every independent set X of size i in G, then there exists a perfect matching in G.

(2) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is extreme in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|i, and |Γ(Y)||U|−i+m+1 for any Y U, |Y|=m (1mi−1).

(3) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is a barrier in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|=i, and |Γ(Y)|m+1 for any Y U, |Y|=m (1mi−1).     

The threshold weight of a graph

The threshold weight of a graph G is introduced as a measure of the amount by which G differs from being a threshold graph. The threshold graphs are precisely the graphs whose threshold weights are 0. At the opposite extreme is the class of graphs for which the threshold weight is the maximum possible. Such graphs are defined as heavy graphs. Among the results are as following: A theorem that specifies the threshold weight of any triangle-free graph; necessary and sufficient conditions for a heavy graph in terms of the solvability of a system of linear inequalities; some sufficient conditions for a graph to be heavy and a necessary condition (conjectured to be sufficient, as well) for a heavy graph in terms of its cliques.