Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G, there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (Mink-CDS). We prove that Mink-CDS is NP-hard on planar bipartite graphs of maximum degree 4. We also prove that Mink-CDS is APX-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for Mink-CDS on bipar- tite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complex- ity of computing this graph parameter. On the positive side, we show an approximation algorithm for Mink-CDS. When k = 1, we present two new approximation algorithms for the weighted version of the problem, one of them restricted to graphs with a poly- nomially bounded number of minimal separators. Finally, also for the weighted variant of the problem where k = 1, we discuss an integer linear programming formulation and conduct a polyhedral study of its associated polytope. / Seja G um grafo conexo e k um inteiro positivo. Um subconjunto D de vértices de G é um conjunto dominante conexo de k-saltos se o subgrafo de G induzido por D é conexo e se, para todo vértice v em G, existe um vértice u em D a uma distância não maior do que k de v. Estudamos neste trabalho o problema de se encontrar um conjunto dominante conexo de k-saltos com cardinalidade mínima (Mink-CDS). Provamos que Mink-CDS é NP-difícil em grafos planares bipartidos com grau máximo 4. Mostramos que Mink-CDS é APX-completo em grafos bipartidos com grau máximo 4. Apresentamos limiares de inaproximabilidade para Mink-CDS para grafos bipartidos e (1, 2)-split, sendo que um desses é expresso em função de um parâmetro independente da ordem do grafo. Também discutimos a complexidade computacional do problema de se computar tal parâmetro. No lado positivo, propomos um algoritmo de aproximação para Mink-CDS cuja razão de aproximação é melhor do que a que se conhecia para esse problema. Finalmente, quando k = 1, apresentamos dois novos algoritmos de aproximação para a versão do problema com pesos nos vértices, sendo que um deles restrito a classes de grafos com um número polinomial de separadores minimais. Além disso, discutimos uma formulação de programação linear inteira para essa versão do problema e provamos resultados poliédricos a respeito de algumas das desigualdades que constituem o politopo associado à formulação.

A highly porous metal–organic framework Cu2(BBCDC) (BBCDC = 9,9′-([1,1′-[b with combining low line]iphenyl]-4,4′-diyl)[b with combining low line]is(9H-[c with combining low line]arbazole-3,6-[d with combining low line]i[c with combining low line]arboxylate) (DUT-49) with a specific surface area of 5476 m2 g−1, a pore volume of 2.91 cm3 g−1, a H2 excess uptake of 80 mg g−1 (77 K, 50 bar), a CO2 excess uptake of 2.01 g g−1 (298 K, 50 bar) and an exceptionally high excess methane storage capacity of 308 mg g−1 (298 K, 110 bar) was obtained using an extended tetratopic linker. / Dieser Beitrag ist mit Zustimmung des Rechteinhabers aufgrund einer (DFG-geförderten) Allianz- bzw. Nationallizenz frei zugänglich.

The quadratic traveling salesman problem (QTSP) is an extension of the (classical) Traveling Salesman Problem (TSP) where the costs depend on each two nodes that are traversed in succession, i. e., on the edges in the symmetric (STSP) and on the arcs in the asymmetric case (ATSP). The QTSP is motivated by an application in bioinformatics. It can be used in the solution of certain Permuted Markov models that are set up for the recognition of transcription factor binding sites and of splice sites in gene regulation. Important special cases are the Angular-Metric TSP used in robotics and the TSP with Reload Costs used in the planning of telecommunication and transport networks. The SQTSP and the AQTSP can be formulated as integer optimization problems over the polytope associated with the STSP resp. ATSP together with a quadratic cost function. We study the polytopes arising from a linearization of the respective quadratic integer programming formulations. Based on the proof of the dimension of the polytopes using the so called direct method we can prove the facetness of several valid inequalities. These facets and valid inequalities can be divided into three large groups. Some are related to the Boolean quadric polytope. Furthermore we introduce the conflicting edges/arc inequalities that forbid certain configurations of edges and 2-edges resp. of arcs and 2-arcs. Finally, we strengthen valid inequalities of STSP and ATSP in order to get stronger inequalities in the quadratic case. We present two general lifting approaches. One is applicable to all inequalities with nonnegative coefficients and the second allows to strengthen clique tree inequalities. Applying these approaches to the subtour elimination constraints leads to facets in most cases, but in general facetness is not preserved. In addition, the complexity of the separation problems for some of the facet classes is studied. Finally, we present some computational results using a branch-and-cut framework, which is improved by some of the newly derived cutting planes. The tested instances from biology could be solved surprisingly well. Instances with up to 100 nodes could be solved in less than 700 seconds improving the results in the literature by several orders of magnitude. For most of the randomly generated instances using some additional separators allowed to reduce the root gaps and the numbers of nodes in the branch-and-cut tree significantly, often even the running times.

This study was carried out to investigate the effect of using animated computer 3-D figures illustration (ACTDFI) in the learning of polyhedron in geometry. By random sampling, intact group of four grade 9 classes in four different schools from a cluster of four educational district schools of Limpopo province in South Africa were selected. The study involved quasi-experimental and inquiry research approaches, the quasi-experimental approach involved pre and posttest design while the inquiry research approach involve classroom observation. There were three experimental groups and a control group with a total of 174 study participants. ACTDFI was used as an intervention for two weeks in the three experimental groups while in the control group, chalk-talk traditional teaching approach was used. Pre-test and post-test was used to collect quantitative data while classroom observation was used to collect qualitative data. This study was carried out to investigate the effect of using animated computer 3-D figures illustration (ACTDFI) in the learning of polyhedron in geometry. By random sampling, intact group of four grade 9 classes in four different schools from a cluster of four educational district schools of Limpopo province in South Africa were selected. The study involved quasi-experimental and inquiry research approaches, the quasi-experimental approach involved pre and posttest design while the inquiry research approach involve classroom observation. There were three experimental groups and a control group with a total of 174 study participants. ACTDFI was used as an intervention for two weeks in the three experimental groups while in the control group, chalk-talk traditional teaching approach was used. Pre-test and post-test was used to collect quantitative data while classroom observation was used to collect qualitative data. The findings from the quantitative Classroom observations were carried out to collect relevant data on how the study participants were taught stationary points in differential calculus, especially with the use of the constructivist pedagogical approach. A suitable observation checklist was developed for this purpose (Appendix 6 refers). Classroom observation checklist is a list of factors to be considered while observing a class. It gives a structure and framework for the observation. suggested that the use of ACTDFI might have improved academic achievement in learning of polyhedron during the intervention, while the qualitative data analysis indicated that the use of ACTDFI in the experimental groups might have facilitated the learning of the concepts of polyhedron. It is therefore recommended that further research is necessary on the application of ACTDFI in the teaching of 3-dimensional shapes at the primary schools / Mathematics Education / M. Sc. (Mathematics Education)

Conselho Nacional de Desenvolvimento Científico e Tecnológico / This study shows the influence of the molecular topology of the crystal of a series of 14 pyrazolo[1,5-a]pyrimidines. The topological data were obtained from X-ray diffraction data and energy stabilization were determined by thermal analysis and chemical computations. Topological analysis carried out was Molecular Coordination Number (NCM) using the Voronoi-Dirichlet polyhedra and Hirshfeld surface. The NCM found for the majority of compounds was 14. Furthermore, it was determined contact area and the solid angle between molecules of the first coordination sphere of the cluster. Several correlations between data were performed, where it is possible highlight the correlation between the area of contact of the cluster molecules and the interaction energy and the solid angle and interaction energy were established. These correlations showed that there is a proportionality between the data, showing that the greater the contact area, the greater the interaction energy for a series of pyrazolo[1,5-a]pyrimidine studied in this thesis. As the contact area, solid angle also presents proportionality with the calculated interaction energy. Among the atom-atom contacts present on the surface of the test compounds was observed that contacts C∙∙∙H and C∙∙∙C are key to stabilize the crystals. This result corroborates the hypothesis that the contact surface between the molecules would be the driving force for the crystalline arrangement. / Este trabalho apresenta o estudo da influência da topologia molecular na organização cristalina de uma série de 14 pirazolo[1,5-a]pirimidinas. Os dados topológicos foram obtidos por difratometria de raios-X e os dados de energia de estabilização foram determinados por análises térmicas e cálculos computacionais. Dentre as análises topológicas realizadas destaca-se a determinação do Número de Coordenação Molecular (NCM) usando o Poliedro de Voronoi-Dirichlet e a Superfície de Hirshfeld. O NMC encontrado para a maioria dos compostos foi de 14. Além disso, foi determinada a área de contato, bem como o ângulo sólido entre as moléculas da primeira esfera de coordenação do cluster. Estabeleceu-se uma serie de correlações entre os dados obtidos, entre elas, destaca-se a correlação entre esta área de contato entre as moléculas do cluster e a energia de interação, bem como a correlação ângulo sólido e energia de interação. Ambas correlações mostraram que há uma proporcionalidade entre os dados, mostrando que quanto maior a área de contato, maior a energia de interação para a série de pirazolo[1,5-a]pirimidinas estudadas nesta dissertação. Assim como a área de contato, o ângulo sólido também apresenta uma proporcionalidade com a energia de interação calculada. Dentre os contatos átomo-átomo presentes na superfície dos compostos em estudo, observou-se que os contatos C∙∙∙H e C∙∙∙C são os principais para a estabilização dos cristais estudados. Este resultado corrobora com a hipótese de que a superfície de contato entre as moléculas seria a força motriz para o arranjo cristalino.

Το πρόβλημα Fermat-Torricelli για n μη συγγραμμικά σημεία με βαρύτητες στον R^3 (b.FT) διατυπώνεται ως εξής: Δοθέντος n μη συγγραμμικών σημείων στον R^3 να βρεθεί ένα σημείο το οποίο ελαχιστοποιεί το άθροισμα των αποστάσεων με θετικές βαρύτητες του σημείου αυτού από τα n δοσμένα σημεία. Το αντίστροφο πρόβλημα Fermat-Torricelli για n μη συγγραμμικά και μη συνεπίπεδα σημεία με βαρύτητες στον R^3 (αντ.FT) διατυπώνεται ως εξής: Δοθέντος ενός σημείου που ανήκει στο εσωτερικό ενός κλειστού πολυέδρου που σχηματίζεται από n δοσμένα μη συγγραμμικά και μη συνεπίπεδα σημεία στον R^3, υπάρχει μοναδικά προσδιορίσιμο σύνολο τιμών για τις βαρύτητες που αντιστοιχούν σε κάθε ένα από τα n δοσμένα σημεία, ώστε το σημείο αυτό να επιλύει για τις τιμές αυτές των βαρυτήτων το πρόβλημα b.FT στον R^3; Στην παρούσα διατριβή, αποδεικνύουμε μία γενίκευση της ισογώνιας ιδιότητας του σημείου b.FT για ένα γεωδαισιακό τρίγωνο σε ένα Κ-επίπεδο (Σφαίρα, Υπερβολικό επίπεδο, Ευκλείδειο επίπεδο). Στη συνέχεια, δίνουμε μία αναγκαία συνθήκη για να είναι το σημείο b.FT εσωτερικό σημείο ενός τετραέδρου και ενός πενταέδρου (πυραμίδες) στον R^3. Η δεύτερη ομάδα αποτελεσμάτων της διατριβής περιλαμβάνει τη θετική απάντηση στο αντ.FT πρόβλημα για τρία μη γεωδαισιακά σημεία στο Κ-επίπεδο και στο αντ.FT πρόβλημα για τέσσερα μη συγγραμμικά και μη συνεπίπεδα σημεία στον R^3. Η αρνητική απάντηση στο αντ.FT για τέσσερα μη συγγραμμικά σημεία στον R^2 θα μας οδηγήσει σε σχέσεις εξάρτησης των βαρυτήτων που ονομάζουμε εξισώσεις της δυναμικής πλαστικότητας των τετραπλεύρων. Ομοίως, δίνοντας αρνητική απάντηση στο αντ.FT πρόβλημα για πέντε μη συνεπίπεδα σημεία στον R^3, παίρνουμε τις εξισώσεις δυναμικής πλαστικότητας , διατυπώνουμε και αποδεικνύουμε την αρχή της πλαστικότητας των κλειστών εξαέδρων στον R^3, που αναφέρει ότι: Έστω ότι πέντε προδιαγεγραμμένα ευθύγραμμα τμήματα συναντώνται στο σημείο b.FT, των οποίων τα άκρα σχηματίζουν ένα κλειστό εξάεδρο. Επιλέγουμε ένα σημείο σε κάθε ημιευθεία που ορίζει το προδιαγεγραμμένο ευθύγραμμο τμήμα, τέτοιο ώστε το τέταρτο σημείο να βρίσκεται πάνω από το επίπεδο που σχηματίζεται από την πρώτη και δεύτερη προδιαγεγραμμένη ημιευθεία και το τρίτο και πέμπτο σημείο να βρίσκονται κάτω από το επίπεδο που σχηματίζεται από την πρώτη και δεύτερη προδιαγεγραμμένη ημιευθεία. Τότε η μείωση της τιμής της βαρύτητας που αντιστοιχεί στην πρώτη, τρίτη και τέταρτη προδιαγεγραμμένη ημιευθεία προκαλεί αύξηση στις βαρύτητες που αντιστοιχούν στη δεύτερη και πέμπτη προδιαγεγραμμένη ημιευθεία.Τέλος, ένα σημαντικό αποτέλεσμα της διατριβής αφορά την επίλυση του γενικευμένου προβλήματος του Gauss για κυρτά τετράπλευρα στο Κ-επίπεδο, θέτοντας δύο σημεία στο εσωτερικό του κυρτού τετραπλεύρου με ίσες βαρύτητες, τα οποία στη συνέχεια αποδεικνύουμε ότι είναι δύο σημεία b.FT με συγκεκριμμένες βαρύτητες, αποτέλεσμα το οποίο γενικεύει το πρόβλημα b.FT για τετράπλευρα στο Κ-επίπεδo. / The weighted Fermat-Torricelli for n non-collinear points in R^3 states the following: Given n non-collinear points in R^3 find a point (b.FT point) which minimizes the sum of the distances multiplied by a positive number which corresponds to a given point (weight). The inverse Fermat-Torricelli problem for n non-collinear points with weights in R^3 (inv.FT) states the following: Given a point that belongs to the interior of a closed polyhedron which is formed between n given non-collinear points in R^3, does there exist a unique set of weights which corresponds to each one of the n points such that this point solves the weighted Fermat-Torricelli problem for this particular set of weights? In the present thesis, we prove a generalization of the isogonal property of the b.FT point for a geodesic triangle on the K-plane (Sphere, Hyperbolic plane, Euclidean plane). We proceed by giving a sufficient condition to locate the b.FT point at the interior of tetrahedra and pentahedra (pyramids) in R^3. The second group of results contains a positive answer on the inv.FT problem for three points that do not belong to a geodesic arc on the K-plane and on the inv.FT problem for four non collinear points and non coplanar in R^3. The negative answer with respect to the inv.FT problem for four non-collinear points in R^2 lead us to the relations of the dependence between the weights that we call the equations of dynamic plasticity for quadrilaterals. Similarly, by giving a negative answer with respect to the inv.FT problem for five points which do not belong in the same plane in R^3, we derive the equations of dynamic plasticity of closed hexahedra and we prove a plasticity principle of closed hexahedra in R^3, which states that: Considering five prescribed rays which meet at the weighted Fermat-Torricelli point, such that their endpoints form a closed hexahedron, a decrease on the weights that correspond to the first, third and fourth ray, causes an increase to the weights that correspond to the second and fifth ray, where the fourth endpoint is upper from the plane which is formed from the first ray and second ray and the third and fifth endpoint is under the plane which is formed from the first ray and second ray. Finally, a significant result of this thesis deals with the solution of the generalized Gauss problem for convex quadrilaterals on the K-plane in which by setting two points at the interior of the convex quadrilateral with equal weights we prove that these points are weighted Fermat-Torricelli points with specific weights, that generalizes the b.FT problem for quadrilaterals on the K-plane.