Currently displaying 1 – 5 of 5

Showing per page

Order by Relevance | Title | Year of publication

On the Vertex Separation of Cactus Graphs

Markov, Minko — 2007

Serdica Journal of Computing

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.

On the Vertex Separation of Maximal Outerplanar Graphs

Markov, Minko — 2008

Serdica Journal of Computing

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.

A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

Markov, MinkoIonut Andreica, MugurelManev, KrassimirTapus, Nicolae — 2012

Serdica Journal of Computing

ACM Computing Classification System (1998): G.2.2. We propose an algorithm that computes the length of a longest path in a cactus graph. Our algorithm can easily be modified to output a longest path as well or to solve the problem on cacti with edge or vertex weights. The algorithm works on rooted cacti and assigns to each vertex a two-number label, the first number being the desired parameter of the subcactus rooted at that vertex. The algorithm applies the divide-and-conquer approach...

Model Mining and Efficient Verification of Software Product Lines

Soleimanifard, SiavashGurov, DilianSchaefer, InaØstvold, BjarteMarkov, Minko — 2015

Serdica Journal of Computing

Software product line modeling aims at capturing a set of software products in an economic yet meaningful way. We introduce a class of variability models that capture the sharing between the software artifacts forming the products of a software product line (SPL) in a hierarchical fashion, in terms of commonalities and orthogonalities. Such models are useful when analyzing and verifying all products of an SPL, since they provide a scheme for divide-and-conquer-style decomposition of the analysis...

Page 1

Download Results (CSV)