Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
Convex graph covers
Authors: Radu Buzatu, Sergiu Cataranciuc
Keywords: Convexity, graphs, convex covers, convex partitions
– 0.35 Mb
Keywords: Convexity, graphs, convex covers, convex partitions
Abstract
We study some properties of minimum convex covers and minimum convex partitions of simple graphs. We establish existence of graphs with fixed number of minimum convex covers and minimum convex partitions. It is known that convex p-cover problem is NP-complete for p\geq3 [5]. We prove that this problem is NP-complete in the case p=2. Also, we study covers and partitions of graphs when respective sets are nontrivial convex.State University of Moldova
60 A. Mateevici, MD-2009, Cișinău, Republic of Moldova
E-mail: ,
60 A. Mateevici, MD-2009, Cișinău, Republic of Moldova
E-mail: ,
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License
Fulltext
– 0.35 Mb
Contents
- Convex graph covers
- Set-theoretic Analysis of Nominative Data
- Admissibility, compatibility, and deducibility in first-order sequent logics
- Small P Systems with Catalysts or Anti-Matter Simulating Generalized Register Machines and Generalized Counter Automata
- Extensionality, Proper Classes, and Quantum Non-Individuality
- Edge detection in digital images using Ant Colony Optimization
- Probability on groups and an application to cryptography
- Classification of Early Stages of NAFLD Based on Dual Diagnostic Methods
- Annotation on PhD Thesis
