The notion of a tolerance is a helpful tool for designing approximation and exact algorithms for solving combinatorial optimization problems. In this paper we suggest a tolerance-based polynomial ...heuristic algorithm for the weighted independent set problem. Several computational experiments show that our heuristics works very well on graphs of a small density.
The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated and most ...important problems on graphs, it is well known to be
NP
-complete and hard to approximate. The complexity of MWIS is open for hole-free graphs (i.e., graphs without induced subgraphs isomorphic to a chordless cycle of length at least five). By applying a combination of clique separator and modular decomposition, we obtain a polynomial time solution of MWIS for hole- and co-chair-free graphs (the co-chair consists of five vertices four of which form a clique minus one edge – a
diamond – and the fifth has degree one and is adjacent to one of the degree two vertices of the diamond).
► The Maximum Weight Independent Set (MWIS) problem on graphs is a frequently studied problem. ► Clique separators and modular decomposition are powerful tools for solving this problem on various graph classes. ► We combine these tools for solving MWIS efficiently on hole- and co-chair-free graphs. ► In particular, we show that prime atoms of those graphs are nearly weakly chordal.
Parallelism in the theoretical computation mainly depends on the particular paradigm or computational environment considered, and its importance has been confirmed with the emergence of each novel ...computing technique. Programmable tile assembly is a novel computing technique to tackle computationally difficult problems, in which computing time grows exponentially corresponding to problematic size. The Maximum independent set（MIS） problem is a typical nondeterministic polynomial problem, which is often associated with strategy applications. In this paper, a novel approach dealing with the MIS problem is proposed based on the abstract tile assembly model, which is believed to be better than the conventional silicon-based computing in solving the same problem. The method can get the solutions of the MIS problem in θ（m ＋ n） time complexity based on θ（mn） distinct tile types.
The notion is introduced of an expanding operator for the independent set problem. This notion is a useful tool for the constructive formation of new cases with the efficient solvability of this ...problem in the family of hereditary classes of graphs and is applied to hereditary parts of the set
Free
({
P
5
,
C
5
}). It is proved that if for a connected graph
G
the problem is polynomial-time solvable in the class
Free
({
P
5
,
C
5
,
G
}) then it remains so in the class
Free
({
P
5
,
C
5
,
G
○
,
G
⊕
K
1,
p
) for every
p
. We also find two new hereditary subsets of
Free
({
P
5
,
C
5
}) with polynomially solvable independent set problem that are not a corollary of applying the revealed operators.
Abstract One of the models for RNA secondary structure prediction is to view it as maximum independent set problem, which can be approximately solved by Hopfield network. However, when predicting ...native molecules, the model is not always accurate and the heuristic method of Hopfield network is not always stable. It is because that the class information is lost and the accuracy is not determined by the number of base pairs only. Secondary structures of non-coding RNAs are believed conservative on the same class. However, software and web servers nowadays for RNA secondary structure prediction do not consider the class information. In this paper, we involve class information in the initialization of Hopfield network. When the initialization is improved, the promising experimental result shows the efficacy and superiority of our proposed methods.
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.
We address the problem of generating detailed conflict-free railway schedules for given sets of train lines and frequencies. To solve this problem for large railway networks, we propose a network ...decomposition into condensation and compensation zones. Condensation zones contain main station areas, where capacity is limited and trains are required to travel with maximum speed. They are connected by compensation zones, where traffic is less dense and time reserves can be introduced for increasing stability. In this paper, we focus on the scheduling problem in condensation zones. To gain structure in the schedule we enforce a time discretisation which reduces the problem size considerably and also the cognitive load of the dispatchers. The problem is formulated as an independent set problem in a conflict graph, which is then solved using a fixed-point iteration heuristic. Results show that even large-scale problems with dense timetables and large topologies can be solved quickly.
This paper, the second one in a three-paper sequence, presents the nesC model of a Hopfield neural network configured for a static optimization problem, the maximum independent set, in fully parallel ...and distributed mode for TinyOS-based wireless sensor networks. Actual nesC code that implements the required neural computing functionality is presented. The graph representation of the maximum independent set problem is used as the basis for the topology of the Hopfield network as well as the wireless sensor network since each mote is conceived to house one neuron in order to facilitate fully parallel and distributed computation. The nesC implementation of a multitude of phases of computation is detailed including initialization of the neural network, relaxation, convergence detection, and solution detection all while the neural computations are performed on the wireless sensor network. Simulation of the presented nesC-TinyOS model is deferred to the third paper in the sequence.
Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional constraints on the number of edges depending on the number of ...vertices. For every natural number
C
, this problem is shown to be polynomially solvable in the class of graphs
On the other hand, this problem is proved to be not polynomially solvable in the class of graphs
for every unbounded nondecreasing function
f
(
n
): ℕ → ℕ, such that exponent of this function grows faster than a polynomial function of
n
. The latter result is true if there does not exist a subexponential algorithm for solving the independent set problem.
PDF
