A Metaheuristic Approach to Solving the Generalized Vertex Cover Problem

AMS Subj. Classification: 90C27, 05C85, 90C59

On the Vertex Folkman Numbers Fv(2,...,2;q)

2000 Mathematics Subject Classification: 05C55.

On the Vertex Separation of Maximal Outerplanar Graphs

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.

On a Class of Vertex Folkman Numbers

Let a1 , . . . , ar, be positive integers, i=1 ... r, m = ∑(ai − 1) + 1 and p = max{a1 , . . . , ar }. For a graph G the symbol G → (a1 , . . . , ar ) means that in every r-coloring of the vertices of G there exists a monochromatic ai -clique of color i for some i ∈ {1, . . . , r}. In this paper we consider the vertex Folkman numbers F (a1 , . . . , ar ; m − 1) = min |V (G)| : G → (a1 , . . . , ar ) and Km−1 ⊂ G} We prove that F (a1 , . . . , ar ; m − 1) = m + 6, if p = 3 and m ≧ 6 (Theorem 3) and F (a1 , . . . , ar ; m − 1) = m + 7, if p = 4 and m ≧ 6 (Theorem 4).

Singular Solutions of Protter’s Problem for a Class of 3-D Hyperbolic Equations

Недю Иванов Попиванов, Алексей Йорданов Николов - През 1952 г. М. Протър формулира нови гранични задачи за вълновото уравнение, които са тримерни аналози на задачите на Дарбу в равнината. Задачите са разгледани в тримерна област, ограничена от две характеристични конуса и равнина. Сега, след като са минали повече от 50 години, е добре известно, че за безброй гладки функции в дясната страна на уравнението тези задачи нямат класически решения, а обобщеното решение има силна степенна особеност във върха на характеристичния конус, която е изолирана и не се разпространява по конуса. Тук ние разглеждаме трета гранична задача за вълновото уравнение с младши членове и дясна страна във формата на тригонометричен полином. Дадена е по-нова от досега известната априорна оценка за максимално възможната особеност на решенията на тази задача. Оказва се, че при по-общото уравнение с младши членове възможната сингулярност е от същия ред като при чисто вълновото уравнение.

A Variable Neighborhood Search Approach for Solving the Maximum Set Splitting Problem

This paper presents a Variable neighbourhood search (VNS) approach for solving the Maximum Set Splitting Problem (MSSP). The algorithm forms a system of neighborhoods based on changing the component for an increasing number of elements. An efficient local search procedure swaps the components of pairs of elements and yields a relatively short running time. Numerical experiments are performed on the instances known in the literature: minimum hitting set and Steiner triple systems. Computational results show that the proposed VNS achieves all optimal or best known solutions in short times. The experiments indicate that the VNS compares favorably with other methods previously used for solving the MSSP. ACM Computing Classification System (1998): I.2.8.