Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Institution
- Keyword
-
- Cographs (2)
- Optimal algorithms (2)
- ART2 neural network (1)
- Dynamical system (1)
- Fixed point (1)
-
- Genetic algorithms (1)
- Greedy algorithms (1)
- Hamitonicity (1)
- Infinite population model (1)
- Isomorphism (1)
- Linear algorrithms (1)
- Linear-time algorithm (1)
- Local density (1)
- Madaline network (1)
- NP-hard problems (1)
- Object motion prediction (1)
- Optimization (1)
- Path cover (1)
- Quantitative prediction (1)
- Resource allocation (1)
- Scheduling (1)
- Transversality (1)
- VLSI (1)
Articles 1 - 5 of 5
Full-Text Articles in Physical Sciences and Mathematics
Finiteness Of The Fixed Point Set For The Simple Genetic Algorithm, Alden H. Wright, Michael D. Vose
Finiteness Of The Fixed Point Set For The Simple Genetic Algorithm, Alden H. Wright, Michael D. Vose
Computer Science Faculty Publications
The infinite population simple genetic algorithm is a discrete dynamical system model of a genetic algorithm. It is conjectured that trajectories in the model always converge to fixed points. This paper shows that an arbitrarily small perturbation of the fitness will result in a model with a finite number of fixed points. Moreover, every sufficiently small perturbation of fimess preserves the finiteness of the fixed point set. These results allow proofs and constructions that require finiteness of the fixed point set. For example, applying the stable manifold theorem to a fixed point requires the hyperbolicity of the differential of the …
A Linear-Time Recognition Algorithm For P4-Reducible Graphs, B. Jamison, S. Olariu
A Linear-Time Recognition Algorithm For P4-Reducible Graphs, B. Jamison, S. Olariu
Computer Science Faculty Publications
The P4-reducible graphs are a natural generalization of the well-known class of cographs, with applications to scheduling, computational semantics, and clustering. More precisely, the P4-reducible graphs are exactly the graphs none of whose vertices belong to more than one chordless path with three edges. A remarkable property of P4-reducible graphs is their unique tree representation up to isomorphism. In this paper we present a linear-time algorithm to recognize P4-reducible graphs and to construct their corresponding tree representation.
An Optimal Path Cover Algorithm For Cographs, R. Lin, S. Olariu
An Optimal Path Cover Algorithm For Cographs, R. Lin, S. Olariu
Computer Science Faculty Publications
The class of cographs, or complement-reducible graphs, arises naturally in many different areas of applied mathematics and computer science. In this paper, we present an optimal algorithm for determining a minimum path cover for a cograph G. In case G has a Hamiltonian path (cycle) our algorithm exhibits the path (cycle) as well.
Linear Time Optimization Algorithms For P4-Sparse Graphs, Beverly Jamison, Stephan Olariu
Linear Time Optimization Algorithms For P4-Sparse Graphs, Beverly Jamison, Stephan Olariu
Computer Science Faculty Publications
Quite often, real-life applications suggest the study of graphs that feature some local density properties. In particular, graphs that are unlikely to have more than a few chordless paths of length three appear in a number of contexts. A graph G is P4-sparse if no set of five vertices in G induces more than one chordless path of length three. P4-sparse graphs generalize both the class of cographs and the class of P4-reducible graphs. It has been shown that P4-sparse graphs can be recognized in time linear in the size of the …
Quantitative Object Motion Prediction By An Art2 And Madaline Combined Neural Network: Concepts And Experiments, Qiuming Zhu, Ahmed Y. Tawfik
Quantitative Object Motion Prediction By An Art2 And Madaline Combined Neural Network: Concepts And Experiments, Qiuming Zhu, Ahmed Y. Tawfik
Computer Science Faculty Publications
An ART2 and a Madaline combined neural network is applied to predicting object motions in dynamic environments. The ART2 network extracts a set of coherent patterns of the object motion by its self-organizing and unsupervised learning features. The identified patterns are directed to the Madaline network to generate a quantitative prediction of the future motion states. The method does not require any presumption of the mathematical models, and is applicable to a variety of situations.