Optimal sequential and parallel algorithms for cut vertices and bridges on trapezoid graphs.
Chen, Hon-Chan (2004)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Chen, Hon-Chan (2004)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Milica Stojanović, Milica Vučković (2007)
Kragujevac Journal of Mathematics
Similarity:
Milanović, Marija (2010)
Mathematica Balkanica New Series
Similarity:
AMS Subj. Classification: 90C27, 05C85, 90C59 The topic is related to solving the generalized vertex cover problem (GVCP) by genetic algorithm. The problem is NP-hard as a generalization of well-known vertex cover problem which was one of the first problems shown to be NP-hard. The definition of the GVCP and basics of genetic algorithms are described. Details of genetic algorithm and numerical results are presented in [8]. Genetic algorithm obtained high quality solutions in...
Donato, Debora, Laura, Luigi, Leonardi, Stefano, Meyer, Ulrich, Millozzi, Stefano, Sibeyn, Jop F. (2006)
Journal of Graph Algorithms and Applications
Similarity:
Milica Stojanović, Milica Vučković (2011)
The Yugoslav Journal of Operations Research
Similarity:
Markov, Minko (2007)
Serdica Journal of Computing
Similarity:
This paper is part of a work in progress whose goal is to construct a fast, practical algorithm for the vertex separation (VS) of cactus graphs. We prove a theorem for cacti", a necessary and sufficient condition for the VS of a cactus graph being k. Further, we investigate the ensuing ramifications that prevent the construction of an algorithm based on that theorem only.
Jiří Rosický (1970)
Archivum Mathematicum
Similarity:
Hopkins, Glenn, Staton, William (1989)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Edith Hemaspaandra, Jörg Rothe, Holger Spakowski (2006)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of , where is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to . To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs...
Markov, Minko (2008)
Serdica Journal of Computing
Similarity:
We investigate the NP-complete problem Vertex Separation (VS) on Maximal Outerplanar Graphs (mops). We formulate and prove a “main theorem for mops”, a necessary and sufficient condition for the vertex separation of a mop being k. The main theorem reduces the vertex separation of mops to a special kind of stretchability, one that we call affixability, of submops.