AMBIENTUM BIOETHICA BIOLOGIA CHEMIA DIGITALIA DRAMATICA EDUCATIO ARTIS GYMNAST. ENGINEERING EPHEMERIDES EUROPAEA GEOGRAPHIA GEOLOGIA HISTORIA HISTORIA ARTIUM INFORMATICA IURISPRUDENTIA MATHEMATICA MUSICA NEGOTIA OECONOMICA PHILOLOGIA PHILOSOPHIA PHYSICA POLITICA PSYCHOLOGIA-PAEDAGOGIA SOCIOLOGIA THEOLOGIA CATHOLICA THEOLOGIA CATHOLICA LATIN THEOLOGIA GR.-CATH. VARAD THEOLOGIA ORTHODOXA THEOLOGIA REF. TRANSYLVAN
|
|||||||
Rezumat articol ediţie STUDIA UNIVERSITATIS BABEŞ-BOLYAI În partea de jos este prezentat rezumatul articolului selectat. Pentru revenire la cuprinsul ediţiei din care face parte acest articol, se accesează linkul din titlu. Pentru vizualizarea tuturor articolelor din arhivă la care este autor/coautor unul din autorii de mai jos, se accesează linkul din numele autorului. |
|||||||
STUDIA INFORMATICA - Ediţia nr.1 din 2016 | |||||||
Articol: |
COVERS OF GRAPHS BY TWO CONVEX SETS. Autori: . |
||||||
Rezumat: VIEW PDF: COVERS OF GRAPHS BY TWO CONVEX SETS The nontrivial convex 2-cover problem of a simple graph is studied. We establish the existence of a convex (2, nt)-cover in dependency of existing convex (2, t)-covers. We prove that it is NP-complete to decide whether a graph that has convex (2, t)-covers also has a convex (2, nt)-cover. In addition, we identify some classes of graphs for which there exists a convex (2, nt)-cover. Keywords and phrases: convexity, convex covers, simplicial vertex, NP-completeness, convex partition. 2010 Mathematics Subject Classification. 05C35, 05C85. |
|||||||