Skip to main content

Research Repository

Advanced Search

All Outputs (2797)

The Recognition of Triangle Graphs (2011)
Presentation / Conference Contribution
Mertzios, G. (2011). The Recognition of Triangle Graphs. In T. Schwentick, & C. Dürr (Eds.), 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, 10-12 March 2011, Dortmund, Germany ; proceedings (591-602). https://doi.org/10.4230/lipics.stacs.2011.591

Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L_{1} and L_{2} of the plane. Strictly between permutation and trapezoid graphs lie the simple-triangle graphs... Read More about The Recognition of Triangle Graphs.

List coloring in the absence of a linear forest (2011)
Presentation / Conference Contribution
Couturier, J. F., Golovach, P. A., Kratsch, D., & Paulusma, D. (2011, December). List coloring in the absence of a linear forest. Presented at 37th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2011, Tepla Monastery, Czech Republic

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The List k -Coloring problem requires in addition that every vertex u must receive a color from some g... Read More about List coloring in the absence of a linear forest.

The computational complexity of Disconnected Cut and 2K2-Partition (2011)
Presentation / Conference Contribution
Martin, B., & Paulusma, D. (2011, December). The computational complexity of Disconnected Cut and 2K2-Partition. Presented at Principles and Practice of Constraint Programming, 17th International Conference, CP 2011, Perugia, Italy

For a connected graph G = (V,E), a subset U ⊆ V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the problem to test whether a graph has a disconnected cut is NP-complete. Thi... Read More about The computational complexity of Disconnected Cut and 2K2-Partition.

Contracting a chordal graph to a split graph or a tree (2011)
Presentation / Conference Contribution
Golovach, P. A., Kaminski, M., & Paulusma, D. (2011, December). Contracting a chordal graph to a split graph or a tree. Presented at 36th International Symposium on Mathematical Foundations of Computer Science 2011, MFCS 2011, Warsaw, Poland

The problems Contractibility and Induced Minor are to test whether a graph G contains a graph H as a contraction or as an induced minor, respectively. We show that these two problems can be solved in |VG|f(|VH|)VGf(VH) time if G is a chordal input gr... Read More about Contracting a chordal graph to a split graph or a tree.

An intersection model for multitolerance graphs: Efficient algorithms and hierarchy (2011)
Presentation / Conference Contribution
Mertzios, G. (2011). An intersection model for multitolerance graphs: Efficient algorithms and hierarchy. In Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 23-25 January 2011, San Francisco ; proceedings (1306-1317)

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in con ict. This class of graphs has attracted many research eorts, mainly due to its interesting structure and its numerous... Read More about An intersection model for multitolerance graphs: Efficient algorithms and hierarchy.

Randomized Diffusion for Indivisible Loads (2011)
Presentation / Conference Contribution
Berenbrink, P., Cooper, C., Friedetzky, T., Friedrich, T., & Sauerwald, T. (2011). Randomized Diffusion for Indivisible Loads. In . D. Randall (Ed.), Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011 (429-439)

We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tok... Read More about Randomized Diffusion for Indivisible Loads.

Satisfiability of acyclic and almost acyclic CNF formulas (II) (2011)
Presentation / Conference Contribution
Ordyniak, S., Paulusma, D., & Szeider, S. (2011, December). Satisfiability of acyclic and almost acyclic CNF formulas (II). Presented at 14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011, Ann Arbor, MI

In the first part of this work (FSTTCS’10) we have shown that the satisfiability of CNF formulas with β-acyclic hypergraphs can be decided in polynomial time. In this paper we continue and extend this work. The decision algorithm for β-acyclic formul... Read More about Satisfiability of acyclic and almost acyclic CNF formulas (II).

Numerical Updates of Lifetimes and Mixing Parameters of B Mesons (2011)
Presentation / Conference Contribution
Lenz, A., Nierste, U., & Gershon, T. (2011). Numerical Updates of Lifetimes and Mixing Parameters of B Mesons. In 6th International Workshop on the CKM Unitarity Triangle, CKM 2010, 6-10 September 2010, University of Warwick ; proceedings

We update the Standard-Model predictions for several quantities related to Bs−B¯s and Bd−B¯d mixing. The mass and width differences in the Bs system read ΔMSMs=(17.3±2.6)ps−1 and ΔΓSMs=(0.087±0.021)ps−1, respectively. The CP asymmetries in flavour-sp... Read More about Numerical Updates of Lifetimes and Mixing Parameters of B Mesons.

Towards musical interaction: 'Schismatics' for e-violin and computer (2011)
Presentation / Conference Contribution
Kanno, M., Hayden, S., Adkins, M., & Isaacs, B. (2011). Towards musical interaction: 'Schismatics' for e-violin and computer.

This paper discusses the evolution of the Max/MSP patch used in schismatics (2007, rev. 2010) for electric violin (Violectra) and computer, by composer Sam Hayden in collaboration with violinist Mieko Kanno. schismatics involves a standard performanc... Read More about Towards musical interaction: 'Schismatics' for e-violin and computer.

A qualitative longitudinal approach to exploring service user experiences of lay-led heath improvement interventions (2011)
Presentation / Conference Contribution
Visram, S., Clarke, C., & White, M. (2011). A qualitative longitudinal approach to exploring service user experiences of lay-led heath improvement interventions.

Lay health advisors (LHAs) have been widely used to deliver primary care and health promotion programmes. Although there is some data to support their efficacy, reviews have consistently found insufficient evidence to assess which LHA strategies are... Read More about A qualitative longitudinal approach to exploring service user experiences of lay-led heath improvement interventions.

Summary of WG4: 'Lifetime, Mixing and Weak Mixing Phase in Charm and Beauty, Including Direct Determination of V_tx (2011)
Presentation / Conference Contribution
Kreps, M., Lenz, A., & Leroy, O. (2011). Summary of WG4: 'Lifetime, Mixing and Weak Mixing Phase in Charm and Beauty, Including Direct Determination of V_tx. In 6th International Workshop on the CKM Unitarity Triangle, CKM 2010, 6-10 September 2010, University of Warwick ; proceedings

We present the summary of the Working Group on lifetimes, mixing and weak mixing phases in charm and beauty mesons at the CKM 2010 workshop. In the past year or so good progress was achieved on both experimental and theoretical sides. While this yiel... Read More about Summary of WG4: 'Lifetime, Mixing and Weak Mixing Phase in Charm and Beauty, Including Direct Determination of V_tx.

Tell me about your childhood...using life grids to gather information on health-related behaviours and experiences across the life course (2011)
Presentation / Conference Contribution
Visram, S., Clarke, C., & White, M. (2011). Tell me about your childhood...using life grids to gather information on health-related behaviours and experiences across the life course.

Socio-economic status and conditions are known to be key determinants of health and inequality. These factors exert influence over the life course, with both past and present health experiences being shaped by the wider social, economic and cultural... Read More about Tell me about your childhood...using life grids to gather information on health-related behaviours and experiences across the life course.

CKM theory status (2011)
Presentation / Conference Contribution
Lenz, A., & Soffer, A. (2011). CKM theory status.

In this talk I review the current status of the CKM matrix. A special emphasis is also given to several discrepancies between experiments and the standard model at the level of about three standard deviations. Recent results that appeared after FPCP2... Read More about CKM theory status.

Wind turbine SCADA alarm pattern recognition (2011)
Presentation / Conference Contribution
Chen, B., Qiu, Y., Feng, Y., Tavner, P., & Song, W. (2011). Wind turbine SCADA alarm pattern recognition. In IET Conference on Renewable Power Generation 2011 (RPG 2011) (363-368). https://doi.org/10.1049/cp.2011.0164

Current wind turbine (WT) studies focus on improving their reliability and reducing the cost of energy, particularly when they are operated offshore. WT Supervisory Control and Data Acquisition (SCADA) systems contain alarm signals providing signific... Read More about Wind turbine SCADA alarm pattern recognition.