Coloring graphs without short cycles and long induced paths

Golovach, P.A.; Paulusma, D.; Song, J.

doi:10.1016/j.dam.2013.12.008

A bioimage informatics QVEST: quick, versatile and easy segmentation & tracking system (2014)
Conference Proceeding
Nelson, C. J., & Obara, B. (2014). A bioimage informatics QVEST: quick, versatile and easy segmentation & tracking system.

Often bioimage informatics solutions are developed on a case-by-case system and, once complete, may not be developed or used in a wide spread of applications. Here we demonstrate how a single image analysis technique can be used to segment objects in... Read More about A bioimage informatics QVEST: quick, versatile and easy segmentation & tracking system.

Accelerating ant colony optimization-based edge detection on the GPU using CUDA (2014)
Conference Proceeding
Dawson, L., & Stewart, I. (2014). Accelerating ant colony optimization-based edge detection on the GPU using CUDA. In Proceedings of the 2014 IEEE Congress on Evolutionary Computation : July 6-11, 2014, Beijing, China (1736-1743). https://doi.org/10.1109/cec.2014.6900638

Ant Colony Optimization (ACO) is a nature-inspired metaheuristic that can be applied to a wide range of optimization problems. In this paper we present the first parallel implementation of an ACO-based (image processing) edge detection algorithm on t... Read More about Accelerating ant colony optimization-based edge detection on the GPU using CUDA.

Random Slicing: Efficient and Scalable Data Placement for Large-Scale Storage Systems (2014)
Journal Article
Miranda, A., Effert, S., Kang, Y., Miller, E. L., Popov, I., Brinkmann, A., …Cortes, T. (2014). Random Slicing: Efficient and Scalable Data Placement for Large-Scale Storage Systems. Transactions on Storage, 10(3), Article 9. https://doi.org/10.1145/2632230

The ever-growing amount of data requires highly scalable storage solutions. The most flexible approach is to use storage pools that can be expanded and scaled down by adding or removing storage devices. To make this approach usable, it is necessary t... Read More about Random Slicing: Efficient and Scalable Data Placement for Large-Scale Storage Systems.

Detecting fixed patterns in chordal graphs in polynomial time (2014)
Journal Article
Belmonte, R., Golovach, P., Heggernes, P., van 't Hof, P., Kaminski, M., & Paulusma, D. (2014). Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica, 69(3), 501-521. https://doi.org/10.1007/s00453-013-9748-5

The Contractibility problem takes as input two graphs G and H, and the task is to decide whether H can be obtained from G by a sequence of edge contractions. The Induced Minor and Induced Topological Minor problems are similar, but the first allows b... Read More about Detecting fixed patterns in chordal graphs in polynomial time.

Solutions for the stable roommates problem with payments (2014)
Journal Article
Biró, P., Bomhoff, M., Golovach, P., Kern, W., & Paulusma, D. (2014). Solutions for the stable roommates problem with payments. Theoretical Computer Science, 540-541, 53-61. https://doi.org/10.1016/j.tcs.2013.03.027

The stable roommates problem with payments has as input a graph G=(V,E)G=(V,E) with an edge weighting w:E→R≥0w:E→R≥0 and the problem is to find a stable solution. A solution is a matching MM with a vector p∈R≥0V that satisfies pu+pv=w(uv)pu+pv=w(uv)... Read More about Solutions for the stable roommates problem with payments.

Ephemeral networks with random availability of links: diameter and connectivity (2014)
Conference Proceeding
Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2014). Ephemeral networks with random availability of links: diameter and connectivity. In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures (267-276). https://doi.org/10.1145/2612669.2612693

In this work we consider temporal networks, the links of which are available only at random times (randomly available temporal networks). Our networks are {\em ephemeral}: their links appear sporadically, only at certain times, within a given maximum... Read More about Ephemeral networks with random availability of links: diameter and connectivity.

Admixed Portrait: Design Intervention to Prompt Reflection on Being Online as a New Parent (2014)
Conference Proceeding
Trujillo-Pisanty, D., Durrant, A., Martindale, S., James, S., & Collomosse, J. (2014). Admixed Portrait: Design Intervention to Prompt Reflection on Being Online as a New Parent. In DIS '14: Proceedings of the 2014 conference on Designing interactive systems (503-512). https://doi.org/10.1145/2598510.2602962

This Pictorial documents the process of designing a device as an intervention within a field study of new parents. The device was deployed in participating parents' homes to invite reflection on their everyday experiences of portraying self and other... Read More about Admixed Portrait: Design Intervention to Prompt Reflection on Being Online as a New Parent.

The Complexity of Valued Constraint Satisfaction (2014)
Journal Article
Jeavons, P., Krokhin, A., & Živný, S. (2014). The Complexity of Valued Constraint Satisfaction. Bulletin of the European Association for Theoretical Computer Science, 113, 21-55

We survey recent results on the broad family of problems that can be cast as valued constraint satisfaction problems. We discuss general methods for analysing the complexity of such problems, give examples of tractable cases, and identify general fea... Read More about The Complexity of Valued Constraint Satisfaction.

Utilising Data-driven Learning in Chemistry Teaching: a Shortcut to Improving Chemical Language Comprehension (2014)
Journal Article
Rees, S., Bruce, M., & Bradley, S. (2014). Utilising Data-driven Learning in Chemistry Teaching: a Shortcut to Improving Chemical Language Comprehension. New Directions in the Teaching of Physical Sciences, 10(1), 12-19. https://doi.org/10.11120/ndir.2014.00028

This article describes the development of the FOCUS project and specific pedagogical strategies to improve understanding of the language of chemistry. The importance of language comprehension skills for success in learning chemistry has recently been... Read More about Utilising Data-driven Learning in Chemistry Teaching: a Shortcut to Improving Chemical Language Comprehension.

Efficiently Handling Skew in Outer Joins on Distributed Systems (2014)
Conference Proceeding
Cheng, L., Kotoulas, S., Ward, T., & Theodoropoulos, T. (2014). Efficiently Handling Skew in Outer Joins on Distributed Systems. In 2014 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid 2014) : Chicago, Illinois, USA, 26-29 May 2014 ; proceedings (295-304). https://doi.org/10.1109/ccgrid.2014.35

Outer joins are ubiquitous in databases and big data systems. The question of how best to execute outer joins in large parallel systems is particularly challenging as real world datasets are characterized by data skew leading to performance issues. A... Read More about Efficiently Handling Skew in Outer Joins on Distributed Systems.

Automated Dynamic Resource Provisioning and Monitoring in Virtualized Large-Scale Datacenter (2014)
Conference Proceeding
Abar, S., Lemarinier, P., Theodoropoulos, G., & OHare, G. (2014). Automated Dynamic Resource Provisioning and Monitoring in Virtualized Large-Scale Datacenter. In 2014 IEEE 28th International Conference on Advanced Information Networking and Applications (AINA) : 13-16 May 2014, University of Victoria, Victoria, Canada (961-970). https://doi.org/10.1109/aina.2014.117

Infrastructure as a Service (IaaS) is a pay-as-you go based cloud provision model which on demand outsources the physical servers, guest virtual machine (VM) instances, storage resources, and networking connections. This article reports the design an... Read More about Automated Dynamic Resource Provisioning and Monitoring in Virtualized Large-Scale Datacenter.

Skew Bisubmodularity and Valued CSPs (2014)
Journal Article
Huber, A., Krokhin, A., & Powell, R. (2014). Skew Bisubmodularity and Valued CSPs. SIAM Journal on Computing, 43(3), 1064-1084. https://doi.org/10.1137/120893549

An instance of the (finite-)valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of values, and a sum of (rational-valued) functions, with each function depending on a subset of the variables. The goal... Read More about Skew Bisubmodularity and Valued CSPs.

The ethical and social implications of personalization technologies for e-learning (2014)
Journal Article
Ashman, H., Brailsford, T., Cristea, A., Sheng, Q. Z., Stewart, C., Toms, E. G., & Wade, V. (2014). The ethical and social implications of personalization technologies for e-learning. Information and Management, 51(6), 819-832. https://doi.org/10.1016/j.im.2014.04.003

Personalization in information systems can be considered beneficial but also ethically and socially harmful. Like many other technologies, the uptake of personalization has been rapid, with inadequate consideration given to its effects. Personalizati... Read More about The ethical and social implications of personalization technologies for e-learning.

Space-Time Matching Algorithms for Interest Management in Distributed Virtual Environments (2014)
Journal Article
Liu, E., & Theodoropoulos, G. (2014). Space-Time Matching Algorithms for Interest Management in Distributed Virtual Environments. ACM Transactions on Modeling and Computer Simulation, 24(3), Article 15. https://doi.org/10.1145/2567922

Interest management in Distributed Virtual Environments (DVEs) is a data-filtering technique designed to reduce bandwidth consumption and therefore enhances the scalability of the system. This technique usually involves a process called interest matc... Read More about Space-Time Matching Algorithms for Interest Management in Distributed Virtual Environments.

Approximating Fixation Probabilities in the Generalized Moran Process (2014)
Journal Article
Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2014). Approximating Fixation Probabilities in the Generalized Moran Process. Algorithmica, 69(1), 78-91. https://doi.org/10.1007/s00453-012-9722-7

We consider the Moran process, as generalized by Lieberman et al. (Nature 433:312–316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability pro... Read More about Approximating Fixation Probabilities in the Generalized Moran Process.

Cue-based aggregation with a mobile robot swarm: a novel fuzzy-based method (2014)
Journal Article
Arvin, F., Turgut, A. E., Bazyari, F., Arikan, K. B., Bellotto, N., & Yue, S. (2014). Cue-based aggregation with a mobile robot swarm: a novel fuzzy-based method. Adaptive Behavior, 22(3), 189-206. https://doi.org/10.1177/1059712314528009

Aggregation in swarm robotics is referred to as the gathering of spatially distributed robots into a single aggregate. Aggregation can be classified as cue-based or self-organized. In cue-based aggregation, there is a cue in the environment that poin... Read More about Cue-based aggregation with a mobile robot swarm: a novel fuzzy-based method.

Packing bipartite graphs with covers of complete bipartite graphs (2014)
Journal Article
Chalopin, J., & Paulusma, D. (2014). Packing bipartite graphs with covers of complete bipartite graphs. Discrete Applied Mathematics, 168, 40-50. https://doi.org/10.1016/j.dam.2012.08.026

For a set SS of graphs, a perfect SS-packing (SS-factor) of a graph GG is a set of mutually vertex-disjoint subgraphs of GG that each are isomorphic to a member of SS and that together contain all vertices of GG. If GG allows a covering (locally bije... Read More about Packing bipartite graphs with covers of complete bipartite graphs.

Mesh Discriminative Features for 3D Steganalysis (2014)
Journal Article
Yang, Y., & Ivrissimtzis, I. (2014). Mesh Discriminative Features for 3D Steganalysis. ACM Transactions on Multimedia Computing, Communications and Applications, 10(3), Article 27. https://doi.org/10.1145/2535555

We propose a steganalytic algorithm for triangle meshes, based on the supervised training of a classifier by discriminative feature vectors. After a normalization step, the triangle mesh is calibrated by one step of Laplacian smoothing and then a fea... Read More about Mesh Discriminative Features for 3D Steganalysis.

ReEnact: Sketch Based Choreographic Design from Archival Dance Footage (2014)
Conference Proceeding
James, S., Fonseca, M. J., & Collomosse, J. (2014). ReEnact: Sketch Based Choreographic Design from Archival Dance Footage. In ICMR '14: Proceedings of International Conference on Multimedia Retrieval (313-320). https://doi.org/10.1145/2578726.2578766

We describe a novel system for synthesising video choreography using sketched visual storyboards comprising human poses (stick men) and action labels. First, we describe an algorithm for searching archival dance footage using sketched pose. We match... Read More about ReEnact: Sketch Based Choreographic Design from Archival Dance Footage.

Coloring graphs without short cycles and long induced paths (2014)
Journal Article
Golovach, P., Paulusma, D., & Song, J. (2014). Coloring graphs without short cycles and long induced paths. Discrete Applied Mathematics, 167, 107-120. https://doi.org/10.1016/j.dam.2013.12.008

For an integer k≥1, a graph G is k-colorable if there exists a mapping c:VG→{1,…,k} such that c(u)≠c(v) whenever u and v are two adjacent vertices. For a fixed integer k≥1, the k-Coloring problem is that of testing whether a given graph is k-colorabl... Read More about Coloring graphs without short cycles and long induced paths.

All Outputs (124)