The search session has expired. Please query the service again.
Displaying 41 –
60 of
155
A unit disk graph is the intersection graph of a family of unit disks in the plane. If the disks do not overlap, it is also a unit coin graph or penny graph. It is known that finding a maximum independent set in a unit disk graph is a NP-hard problem. In this work we extend this result to penny graphs. Furthermore, we prove that finding a minimum clique partition in a penny graph is also NP-hard, and present two linear-time approximation algorithms for the computation of clique partitions: a 3-approximation...
A unit disk graph is the intersection graph
of a family of unit disks in the plane.
If the disks do not overlap, it is also a unit coin graph or penny graph.
It is known that finding a maximum independent set
in a unit disk graph is a NP-hard problem.
In this work we extend this result to penny graphs.
Furthermore, we prove that finding a minimum clique partition
in a penny graph is also NP-hard, and present
two linear-time approximation algorithms for the computation of clique partitions:
a 3-approximation...
In this note, we strengthen the inapproximation bound of O(logn) for the labeled perfect matching problem established in J.
Monnot, The Labeled perfect matching in bipartite graphs, Information Processing Letters96 (2005) 81–88, using a
self improving operation in some hard instances. It is interesting
to note that this self improving operation does not work for all
instances. Moreover, based on this approach we deduce that the
problem does not admit constant approximation algorithms for
connected...
A major drawback of orthogonal frequency division multiplexing (OFDM) signals is the high value of peak to average power ratio (PAPR). Partial transmit sequences (PTS) is a popular PAPR reduction method with good PAPR reduction performance, but its search complexity is high. In this paper, in order to reduce PTS search complexity we propose a new technique based on biogeography-based optimization (BBO). More specifically, we present a new Generalized Oppositional Biogeography Based Optimization...
This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...
This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...
A module for conflict detection in A-SMGCS is presented. It supervises the operations that the ground controller has to perform. It doesn?t depend on the topology of the terminal area. The system guarantees the safety of the proposed situation, that is, the impossibility that a conflict arises among aircrafts (and also road vehicles) obeying the signaling. We suppose that the terminal area has stop bars (or semaphores) controlling all intersections and accesses between runways, taxiways, exits,...
The HP model is one of the most popular discretized models for attacking the protein folding problem,
i.e., for the computational prediction of the tertiary structure of a protein from its amino acid
sequence. It is based on the assumption that interactions between hydrophobic amino acids are the main
force in the folding process. Therefore, it distinguishes between polar and hydrophobic amino acids only and
tries to embed the amino acid sequence into a two- or three-dimensional grid lattice...
In this article we describe our experiences with a parallel Singular implementation of the signature of a surface singularity defined by z N + g(x; y) = 0.
Currently displaying 41 –
60 of
155