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.

Many-Valued Logic and Qualitative Modelling of Electrical Circuits

Lee M.H., Many-Valued Logic and Qualitative Modelling of Electrical Circuits, in Proc. QR?2000, 14th Int. Workshop on Qualitative Reasoning, Morelia, Mexico June 3rd - 7th 2000.

On Models, Modelling and the Distinctive Nature of Model-Based Reasoning

M.H. Lee, On Models, Modelling and the Distinctive Nature of Model-Based Reasoning, AI Communications, 12 (3), pp127-137.1999.

Innovation in Ireland's 'high-technology' businesses: the roles of interaction and proximity

This thesis explores the drivers of innovation in Irish high-technology businesses and estimates, in particular, the relative importance of interaction with external businesses and other organisations as a source of knowledge for innovation at the business-level. The thesis also examines the extent to which interaction for innovation in these businesses occurs on a local or regional basis. The study uses original survey data of 184 businesses in the Chemical and Pharmaceutical, Information and Communications Technology and Engineering and Electronic Devices sectors. The study considers both product and process innovation at the level of the business and develops new measures of innovation output. For the first time in an Irish study, the incidence and frequency of interaction is measured for each of a range of agents, other group companies, suppliers, customers, competitors, academic-based researchers and innovation-supporting agencies. The geographic proximity between the business and each of the most important of each of each category of agent is measured using average one-way driving distance, which is the first time such a measure has been used in an Irish study of innovation. Utilising econometric estimation techniques, it is found that interaction with customers, suppliers and innovation-supporting agencies is positively associated with innovation in Irish high-technology businesses. Surprisingly, however, interaction with academic-based researchers is found to have a negative effect on innovation output at the business-level. While interaction generally emerges as a positive influence on business innovation, there is little evidence that this occurs at a local or regional level. Furthermore, there is little support for the presence of localisation economies for high-technology sectors, though some tentative evidence of urbanisation economies. This has important implications for Irish regional, enterprise and innovation policy, which has emphasised the development of clusters of internationally competitive businesses. The thesis brings into question the suitability of a cluster-driven network based approach to business development and competitiveness in an Irish context.

Association for Learning Technology Annual Survey 2014 Data and Report

This is the first report from ALT’s new Annual Survey launched in December 2014. This survey was primarily for ALT members (individual or at an organisation which is an organisational member) it could however also be filled in by others, perhaps those interested in taking out membership. The report and data highlight emerging work areas that are important to the survey respondents. Analysis of the survey responses indicates a number of areas ALT should continue to support and develop. Priorities for the membership are ‘Intelligent use of learning technology’ and ‘Research and practice’, aligned to this is the value placed by respondent’s on by communication via the ALT Newsletter/News, social media and Research in Learning Technology. The survey also reveals ‘Data and Analytics’ and ‘Open Education’ are areas where the majority of respondents are finding are becoming increasingly important. As such our community may benefit from development opportunities ALT can provide. The survey is also a reminder that ALT has an essential role in enabling members to develop research and practice in areas which might be considered as minority interest. For example whilst the majority of respondents didn't indicate areas such as ‘Digital and Open Badges’, and ‘Game Based Learning’ as important there are still members who consider these areas are very significant and becoming increasingly valuable and as such ALT will continue to better support these groups within our community. Whilst ALT has conducted previous surveys of ALT membership this is the first iteration in this form. ALT has committed to surveying the sector on an annual basis, refining the core question set but trying to preserve an opportunity for longitudinal analysis.

Dissidents with an innovation cause? Non-institutionalized actors ’ online social knowledge sharing, solution-finding tensions and technology management innovation

Purpose
– Traditionally, most studies focus on institutionalized management-driven actors to understand technology management innovation. The purpose of this paper is to argue that there is a need for research to study the nature and role of dissident non-institutionalized actors’ (i.e. outsourced web designers and rapid application software developers). The authors propose that through online social knowledge sharing, non-institutionalized actors’ solution-finding tensions enable technology management innovation.

Design/methodology/approach
– A synthesis of the literature and an analysis of the data (21 interviews) provided insights in three areas of solution-finding tensions enabling management innovation. The authors frame the analysis on the peripherally deviant work and the nature of the ways that dissident non-institutionalized actors deviate from their clients (understood as the firm) original contracted objectives.

Findings
– The findings provide insights into the productive role of solution-finding tensions in enabling opportunities for management service innovation. Furthermore, deviant practices that leverage non-institutionalized actors’ online social knowledge to fulfill customers’ requirements are not interpreted negatively, but as a positive willingness to proactively explore alternative paths.

Research limitations/implications
– The findings demonstrate the importance of dissident non-institutionalized actors in technology management innovation. However, this work is based on a single country (USA) and additional research is needed to validate and generalize the findings in other cultural and institutional settings.

Originality/value
– This paper provides new insights into the perceptions of dissident non-institutionalized actors in the practice of IT managerial decision making. The work departs from, but also extends, the previous literature, demonstrating that peripherally deviant work in solution-finding practice creates tensions, enabling management innovation between IT providers and users.

Technology, work organisation and job quality in the service sector: an introduction’

This special issue volume is concerned with how technology is changing the nature of work and working conditions while generating new products and new forms of service delivery. The five articles included in this volume cover service work, from the routine and clerical through to highly credentialed and professional work. Although some of the established challenges concerning the impact of Information and Communication Technology (ICT) on work and workplaces are evident in the articles, it is also clear that new service delivery processes demand new skills and training to some extent. Overall findings indicate that while ICT competencies are important, they need to be supplemented by the soft skills that are crucial for effective customer interactions and more open work systems with greater autonomy and participation whereby flexible work teams can have a positive impact on job quality outcomes. This introductory article examines technology and the changing nature of work through three strands of interpretation, prior to introducing the five articles in this special issue.

The CACTOS Vision of Context-Aware Cloud Topology Optimization and Simulation

Recent advances in hardware development coupled with the rapid adoption and broad applicability of cloud computing have introduced widespread heterogeneity in data centers, significantly complicating the management of cloud applications and data center resources. This paper presents the CACTOS approach to cloud infrastructure automation and optimization, which addresses heterogeneity through a combination of in-depth analysis of application behavior with insights from commercial cloud providers. The aim of the approach is threefold: to model applications and data center resources, to simulate applications and resources for planning and operation, and to optimize application deployment and resource use in an autonomic manner. The approach is based on case studies from the areas of business analytics, enterprise applications, and scientific computing.

Construction studies in higher education and the use of digital technology

The construction industry wants graduate employees skilled in relationship building and information technology and communications (ITC). Much of the relationship building at universities has evolved through technology. Government and the ITC industry fund lobby groups to influence both educational establishments and Government to incorporate more ITC in education _ and ultimately into the construction industry. This influencing ignores the technoskeptics’ concerns about student disengagement through excessive online distractions. Construction studies students (n=64) and lecturers (n=16) at a construction university were surveyed to discover the impact of the use and applications of ITC. Contrary to Government and industry technopositivism, construction students and lecturers preferred hard copy documents to online feedback for assignments and marking, more human interface and less technological substitution and to be on campus for lectures and face-to-face meetings rather than viewing on-screen. ITC also distracted users from tasks which, in the case of students, prevented the development of the concentration and deep thinking which a university education should deliver. The research findings are contrary to the promotions of Government, ITC industry and ITC departments and have implications for construction employers where a renewed focus on human communication should mean less stress, fewer delays and cost overruns.

Philosophies, traditional pedagogy, and new technologies: a report on a case study of EAP teachers' integration of technology into traditional practice

This chapter reports on a study of teachers in transition, developing their practice and their cognitions regarding the integration of learning technologies with traditional approaches to the teaching of English for Academic Purposes (EAP). Taking a case study approach, it examines developments in the practice of three teachers during and after a teacher education programme on the use of technology in the EAP classroom. This is a study of cognition, teaching philosophy, and the relationship between pedagogy, technology, and content, and how teachers situate these within their own practice. The setting is the rapidly changing UK higher education environment, where the speed of change is such that today's latest fashions and gadgets may well be yesterday's news tomorrow. Thus, this is not a tale of individual technologies or tools to make teachers' lives better. This is a story of people, of pedagogy's traditional values intersecting with technology, and the issues arising from this, alongside the evolution of strategies for dealing with these issues.