Cubicity, degeneracy, and crossing number

A $k$-box $B=(R_1,...,R_k)$, where each $R_i$ is a closed interval on the real line, is defined to be the Cartesian product $R_1\times R_2\times ...\times R_k$. If each $R_i$ is a unit length interval, we call $B$ a $k$-cube. Boxicity of a graph $G$, denoted as $\boxi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-boxes. Similarly, the cubicity of $G$, denoted as $\cubi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-cubes. It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan: Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/ 0607092, 2006.] that, for a graph $G$ with maximum degree $\Delta$, $\cubi(G)\leq \lceil 4(\Delta +1)\log n\rceil$. In this paper, we show that, for a $k$-degenerate graph $G$, $\cubi(G) \leq (k+2) \lceil 2e \log n \rceil$. Since $k$ is at most $\Delta$ and can be much lower, this clearly is a stronger result. This bound is tight. We also give an efficient deterministic algorithm that runs in $O(n^2k)$ time to output a $8k(\lceil 2.42 \log n\rceil + 1)$ dimensional cube representation for $G$. An important consequence of the above result is that if the crossing number of a graph $G$ is $t$, then $\boxi(G)$ is $O(t^{1/4}{\lceil\log t\rceil}^{3/4})$ . This bound is tight up to a factor of $O((\log t)^{1/4})$. We also show that, if $G$ has $n$ vertices, then $\cubi(G)$ is $O(\log n + t^{1/4}\log t)$. Using our bound for the cubicity of $k$-degenerate graphs we show that cubicity of almost all graphs in $\mathcal{G}(n,m)$ model is $O(d_{av}\log n)$, where $d_{av}$ denotes the average degree of the graph under consideration. model is O(davlogn).

Rainbow connectivity: hardness and tractability

A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph is (strongly) rainbow connected if there exists a (geodesic) rainbow path between every pair of vertices. The (strong) rainbow connectivity of a graph G, denoted by (src(G), respectively) rc(G) is the smallest number of colors required to edge color the graph such that G is (strongly) rainbow connected. In this paper we study the rainbow connectivity problem and the strong rainbow connectivity problem from a computational point of view. Our main results can be summarised as below: 1) For every fixed k >= 3, it is NP-Complete to decide whether src(G) <= k even when the graph G is bipartite. 2) For every fixed odd k >= 3, it is NP-Complete to decide whether rc(G) <= k. This resolves one of the open problems posed by Chakraborty et al. (J. Comb. Opt., 2011) where they prove the hardness for the even case. 3) The following problem is fixed parameter tractable: Given a graph G, determine the maximum number of pairs of vertices that can be rainbow connected using two colors. 4) For a directed graph G, it is NP-Complete to decide whether rc(G) <= 2.

Fast acoustic likelihood computation using low-rank matrix approximation

Acoustic modeling using mixtures of multivariate Gaussians is the prevalent approach for many speech processing problems. Computing likelihoods against a large set of Gaussians is required as a part of many speech processing systems and it is the computationally dominant phase for LVCSR systems. We express the likelihood computation as a multiplication of matrices representing augmented feature vectors and Gaussian parameters. The computational gain of this approach over traditional methods is by exploiting the structure of these matrices and efficient implementation of their multiplication.In particular, we explore direct low-rank approximation of the Gaussian parameter matrix and indirect derivation of low-rank factors of the Gaussian parameter matrix by optimum approximation of the likelihood matrix. We show that both the methods lead to similar speedups but the latter leads to far lesser impact on the recognition accuracy. Experiments on a 1138 word vocabulary RM1 task using Sphinx 3.7 system show that, for a typical case the matrix multiplication approach leads to overall speedup of 46%. Both the low-rank approximation methods increase the speedup to around 60%, with the former method increasing the word error rate (WER) from 3.2% to 6.6%, while the latter increases the WER from 3.2% to 3.5%.

An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction

23 p. -- An extended abstract of this work appears in the proceedings of the 2012 ACM/IEEE Symposium on Logic in Computer Science

An architecture of multiple heterogeneous case-based reasoning employing agent technologies

This paper presents an investigation into applying Case-Based Reasoning to Multiple Heterogeneous Case Bases using agents. The adaptive CBR process and the architecture of the system are presented. A case study is presented to illustrate and evaluate the approach. The process of creating and maintaining the dynamic data structures is discussed. The similarity metrics employed by the system are used to support the process of optimisation of the collaboration between the agents which is based on the use of a blackboard architecture. The blackboard architecture is shown to support the efficient collaboration between the agents to achieve an efficient overall CBR solution, while using case-based reasoning methods to allow the overall system to adapt and “learn” new collaborative strategies for achieving the aims of the overall CBR problem solving process.

Normdaten im Semantic Web - Konzept für eine Ontologie der Personennamendatei (PND)

Das Ziel dieser Arbeit ist es, ein Konzept für eine Darstellung der Personennamendatei(PND) in den Sprachen Resource Description Framework (RDF), Resource DescriptionFramework Schema Language (RDFS) und Web Ontology Language (OWL) zu entwickeln. Der Prämisse des Semantic Web folgend, Daten sowohl in menschenverständlicher als auch in maschinell verarbeitbarer Form darzustellen und abzulegen, wird eine Struktur für Personendaten geschaffen. Dabei wird von der bestehenden Daten- und Struktursituation im Pica-Format ausgegangen. Die Erweiterbarkeit und Anpassbarkeit des Modells im Hinblick auf zukünftige, im Moment gegebenenfalls noch nicht absehbare Anwendungen und Strukurveränderungen, muss aber darüber hinaus gewährleistet sein. Die Modellierung orientiert sich an bestehenden Standards wie Dublin Core, Friend Of A Friend (FOAF), Functional Requirements for Bibliographic Records (FRBR), Functional Requirements for Authority Data (FRAD) und Resource Description and Access (RDA).

Ergebnisse einer Expertenbefragung zu den Arbeitsmarktpotenzialen im betrieblichen Gesundheitsmanagement

Das Institut für Gesundheitsmanagement (IGM) der Fakultät IV (Wirtschaft und Informatik) der Fachhochschule Hannover hat im Auftrag der Wirtschaftsförderungsgesellschaft „hannoverimpuls“ ein Projekt zum Thema „betriebliches Gesundheitsmanagement – Ansatzpunkte für Arbeitsmarktpotenziale in der Region Hannover“ durchgeführt und im Oktober 2008 mit Übergabe des Projektberichts abgeschlossen. Im Rahmen dieses Projektes wurden u. a. gezielt Experten zum betrieblichen Gesundheitsmanagement (BGM) aus bestehenden und neu erschlossenen Kontakten recherchiert und zur Teilnahme an einer telefonischen bzw. persönlichen Expertenbefragung motiviert. Ziel dieser empirischen Untersuchung war es herauszufinden, ob und ggf. wo genau Arbeitsmarktpotenziale durch BGM nach Einschätzung verschiedener Marktkenner existieren? Der nun vorgelegte Arbeitsbericht dokumentiert ausführlich die Ergebnisse dieser Expertenbefragung.

Technik der verlorenen Briefe: Einfluss der Studienrichtung auf das altruistische Verhalten von Studierenden

Altruistisches Verhalten ist ein fester Bestandteil im Leben von Menschen. Die Bereitschaft sich gegenseitig zu unterstützen ist durch unterschiedliche Motive gekennzeichnet. Manche Menschen helfen, ohne einen eigenen Nutzen daraus zu ziehen. Andere Menschen dagegen verhalten sich in gewissem Maße hilfsbereit, erwarten hierfür aber eine Gegenleistung. Die vorliegende Arbeit untersucht die altruistischen Verhaltensweisen von Studierenden verschiedener Fachrichtungen. Basierend auf der Technik der verlorenen Briefe wurde in einem Feldexperiment das altruistische Verhalten von Studierenden der Fakultät IV (Wirtschaft und Informatik) und der Fakultät V (Diakonie, Gesundheit und Soziales) der Hochschule Hannover untersucht. Dabei wurden Briefe an unterschiedlichen Stellen platziert und deren Mitnahme- und Rücklaufergebnis gemessen. Die Ergebnisse zeigen, dass Studierende der Fakultät IV (Wirtschaft und Informatik) eher zu altruistischem Verhalten neigen, als die durch ihren Studiengang vermeintlich stärker sozial geprägten Studierenden der Fakultät V (Diakonie, Gesundheit und Soziales). Ferner nimmt die Wahrscheinlichkeit eines altruistischen Verhaltens mit steigender Anzahl an anwesenden Personen ab.

Intrinsische und extrinsische Motivation von Studierenden der Hochschule Hannover : Messung an den Fakultäten III und IV

Bei der vorliegenden Arbeit handelt es sich um eine überarbeitete Version einer Hausarbeit im Modul Research Management im Masterstudiengang Unternehmensentwicklung im Sommersemester 2014 bei Prof. Dr. Sven Litzcke. In der Arbeit wird untersucht, ob die oftmals vorherrschende Meinung zutrifft, dass Studierende wirtschaftsorientierter Studiengänge ihre Studiengangwahl aufgrund der positiven Karriere- und Verdienstmöglichkeiten und unter Vernachlässigung ihrer persönlichen Neigungen und Interessen getroffen haben. Mittels eines Fragebogens werden die Ausprägungen der Motivationsformen extrinsische und intrinsische Motivation von Studierenden der Fakultät IV Wirtschaft und Informatik der Hochschule Hannover gemessen. Da Studierenden von künstlerischen und kreativen Studiengängen dieses Verhalten nicht unterstellt wird, werden Studierende der Fakultät III Medien, Information und Design der Hochschule Hannover als Vergleichsgruppe herangezogen. Die Untersuchung orientiert sich an der Hypothese, dass die extrinsische Motivation von Studierenden der Fakultät IV der Hochschule Hannover in Bezug auf ihr Studium stärker ausgeprägt ist als die von Studierenden an der Fakultät III der Hochschule Hannover. Da vermutet wird, dass die Fakultät IV der Hochschule Hannover nicht aus einer homogenen Gruppe besteht, untersucht diese Arbeit zudem die Hypothese, dass die extrinsische Motivation von Studierenden im Studiengang Betriebswirtschaftslehre in Bezug auf ihr Studium stärker ausgeprägt ist, als die von Studierenden der Angewandten Informatik. Die Auswertung von 312 Fragebögen hat beide Hypothesen bestätigt. Studierende der Fakultät III sind weniger extrinsisch und stärker intrinsisch motiviert als Studierende der Fakultät IV. Zudem sind Studierende der Betriebswirtschaftslehre an der Hochschule Hannover stärker extrinsisch motiviert als Studierende der Angewandten Informatik an der Hochschule Hannover.

E-Assessment mit Graja – ein Vergleich zu Anforderungen an Softwaretestwerkzeuge

Die automatisierte Bewertung studentischer Übungsabgaben in Programmieren-Lehrveranstaltungen weist Parallelen zum automatisierten Test in der professionellen Softwareentwicklung auf. Allerdings muss ein Autobewerter (Grader), um lernförderlich zu sein, andere Zielsetzungen erfüllen als üblicherweise im professionellen Softwaretest eingesetzte Analyse- und Testwerkzeuge. Dieser Beitrag identifiziert wesentliche Unterschiede und beschreibt, wie sich diese Unterschiede in dem an der Hochschule Hannover entwickelten und seit mehreren Jahren im Einsatz befindlichen Autobewerter "Graja" niederschlagen.

Code for competence - Programmieren für Zweitklässler mit ScratchJr

Wir beschreiben und belegen anhand eines Pilotprojekts in einer zweiten Grundschulklasse, dass Informatik in der Grundschule das Potential hat, fächerübergreifend Kompetenzen in fast allen Fächern des Grundschulkanons zu fördern. Wir erläutern mehrere Unterrichtseinheiten eines ScratchJr-Einsatzes und dokumentieren positive Wirkungen auf vielfältige Kompetenzen, die Kinder im Grundschulalter erwerben sollen. Der Beitrag stellt einen Erfahrungsbericht und qualitative Ergebnisse zur Verfügung. Eingesetzte Arbeitsmaterialien werden online zur Verfügung gestellt. Die bisherigen positiven Erfahrungen haben uns veranlasst, die Arbeit mit ScratchJr in der Pilotklasse auf mehrere Monate auszudehnen.

A review of dynamic Bayesian network techniques with applications in healthcare risk modelling

Coping with an ageing population is a major concern for healthcare organisations around the world. The average cost of hospital care is higher than social care for older and terminally ill patients. Moreover, the average cost of social care increases with the age of the patient. Therefore, it is important to make efficient and fair capacity planning which also incorporates patient centred outcomes. Predictive models can provide predictions which their accuracy can be understood and quantified. Predictive modelling can help patients and carers to get the appropriate support services, and allow clinical decision-makers to improve care quality and reduce the cost of inappropriate hospital and Accident and Emergency admissions. The aim of this study is to provide a review of modelling techniques and frameworks for predictive risk modelling of patients in hospital, based on routinely collected data such as the Hospital Episode Statistics database. A number of sub-problems can be considered such as Length-of-Stay and End-of-Life predictive modelling. The methodologies in the literature are mainly focused on addressing the problems using regression methods and Markov models, and the majority lack generalisability. In some cases, the robustness, accuracy and re-usability of predictive risk models have been shown to be improved using Machine Learning methods. Dynamic Bayesian Network techniques can represent complex correlations models and include small probabilities into the solution. The main focus of this study is to provide a review of major time-varying Dynamic Bayesian Network techniques with applications in healthcare predictive risk modelling.

La résistance bactérienne aux antibiotiques.

50 years ago, the introduction of penicillin, followed by many other antibacterial agents, represented an often underestimated medical revolution. Indeed, until that time, bacterial infections were the prime cause of mortality, especially in children and elderly patients. The discovery of numerous new substances and their development on an industrial scale gave us the illusion that bacterial infections were all but vanquished. However, the widespread and sometimes uncontrolled use of these agents has led to the selection of bacteria resistant to practically all available antibiotics. Bacteria utilize three main resistance strategies: (1) modification of their permeability, (2) modification of target, and (3) modification of the antibiotic. Bacteria modify their permeability either by becoming impermeable to antibiotics, or by actively excreting the drug accumulated in the cell. As an alternative, they can modify the structure of the antibiotic's molecular target--usually an essential metabolic enzyme of the bacterium--and thus escape the drug's toxic effect. Lastly, they can produce enzymes capable of modifying and directly inactivating antibiotics. In addition, bacteria have evolved extremely efficient genetic transfer systems capable of exchanging and accumulating resistance genes. Some pathogens, such as methicillin-resistant Staphylococcus aureus and multiresistant Mycobacterium tuberculosis, have become resistant to almost all available antibiotics and there are only one or two substances still active against such organisms. Antibiotics are very precious drugs which must be administered to patients who need them. On the other hand, the development of resistance must be kept under control by a better comprehension of its mechanisms and modes of transmission and by abiding by the fundamental rules of anti-infectious chemotherapy, i.e.: (1) choose the most efficient antibiotic according to clinical and local epidemiological data, (2) target the bacteria according to the microbiological data at hand, and (3) administer the antibiotic in an adequate dose which will leave the pathogen no chance to develop resistance.

Utilisation de la coronarographie en Suisse: une étude de population. [The use of coronary vessel radiography in Switzerland: a population study].

All patients having undergone a coronarography during 1984 have been surveyed in Switzerland. This retrospective study has used existing data in the 13 centers practicing this diagnostic procedure. 4921 coronarographies were carried out in 1984, amongst 4359 patients. In terms of population-based rates, the national figures are 77 procedures/100,000 residents, and 68 patients/100,000 residents. Female rates are one fourth of the male rates (27/100,000 versus 112/100,000). For both sexes, the highest utilization rates are for the age groups 60-64. Swiss figures are relatively low when compared with other developed countries. However, patterns of utilization are very different within the country: according to the Canton of residence of the patient, the utilization rates (standardized for age and sex) vary from 8/100,000 to 160/100,000. There is a distinct gradient from south-west to north-east, which closely corresponds to the distribution of centers practicing the procedure. More intriguing is the fact that cardiovascular mortality shows an inverse geographical gradient, with the highest mortality in Cantons having the lowest rate of coronarography. Various reasons for the observed variations are discussed, in relation with differences in supply of diagnostic and therapeutic equipments, but also in relation with various patterns of demand related to differential morbidity rates and/or differential patterns of clinical decision.