Skip to main content

Research Repository

Advanced Search

Outputs (3168)

L(2,1,1)-labeling is NP-complete for trees (2010)
Presentation / Conference Contribution
Golovach, P. A., Lidicky, B., & Paulusma, D. (2010, December). L(2,1,1)-labeling is NP-complete for trees. Presented at 7th Annual Conference on Theory and Applications of Models of Computation, Prague, Czech Republic

An L(p 1,p 2,p 3)-labeling of a graph G with span λ is a mapping f that assigns each vertex u of G an integer label 0 ≤ f(u) ≤ λ such that |f(u) − f(v)| ≥ p i whenever vertices u and v are of distance i for i ∈ {1,2,3}. We show that testing whether a... Read More about L(2,1,1)-labeling is NP-complete for trees.

On contracting graphs to fixed pattern graphs (2010)
Presentation / Conference Contribution
't, H. P. V., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. M. (2010, December). On contracting graphs to fixed pattern graphs. Presented at 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindleruv Mlýn, Czech Republic

For a fixed graph H, the H-Contractibility problem asks if a graph is H-contractible, i.e., can be transformed into H via a series of edge contractions. The computational complexity classification of this problem is still open. So far, H has a domina... Read More about On contracting graphs to fixed pattern graphs.

On solution concepts for matching games (2010)
Presentation / Conference Contribution
Biro, P., Kern, W., & Paulusma, D. (2010, December). On solution concepts for matching games. Presented at 7th Annual Conference on Theory and Applications of Models of Computation, Prague, Czech Republic

A matching game is a cooperative game (N,v) defined on a graph G = (N,E) with an edge weighting . The player set is N and the value of a coalition S ⊆ N is defined as the maximum weight of a matching in the subgraph induced by S. First we present an... Read More about On solution concepts for matching games.

Implicit surface reconstruction and feature detection with a learning algorithm (2010)
Presentation / Conference Contribution
Kaye, D., & Ivrissimtzis, I. (2010, September). Implicit surface reconstruction and feature detection with a learning algorithm. Presented at Theory and Practice of Computer Graphics, Sheffield, UK

We propose a new algorithm for implicit surface reconstruction and feature detection. The algorithm is based on a self organising map with the connectivity of a regular 3D grid that can be trained into an implicit representation of surface data. The... Read More about Implicit surface reconstruction and feature detection with a learning algorithm.

Packing bipartite graphs with covers of complete bipartite graphs (2010)
Presentation / Conference Contribution
Chalopin, J., & Paulusma, D. (2010, December). Packing bipartite graphs with covers of complete bipartite graphs. Presented at 7th International Conference on Algorithms and Complexity, Rome, Italy

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

The k-in-a-path problem for claw-free graphs (2010)
Presentation / Conference Contribution
Fiala, J., Kaminski, M., Lidicky, B., & Paulusma, D. (2010, December). The k-in-a-path problem for claw-free graphs. Presented at 27th International Symposium on Theoretical Aspects of Computer Science, Nancy, France

Testing whether there is an induced path in a graph spanning $k$ given vertices is already \NP-complete in general graphs when $k=3$. We show how to solve this problem in polynomial time on claw-free graphs, when $k$ is not part of the input but an a... Read More about The k-in-a-path problem for claw-free graphs.

Contractions of planar graphs in polynomial time (2010)
Presentation / Conference Contribution
Kaminski, M., Paulusma, D., & Thilikos, D. (2010, December). Contractions of planar graphs in polynomial time. Presented at The 18th Annual European Symposium

We prove that for every graph H, there exists a polynomial-time algorithm deciding if a planar graph can be contracted to H. We introduce contractions and topological minors of embedded (plane) graphs and show that a plane graph H is an embedded cont... Read More about Contractions of planar graphs in polynomial time.

Effects of Noise on Quantized Triangle Meshes (2010)
Presentation / Conference Contribution
Ivrissimtzis, I. (2010, December). Effects of Noise on Quantized Triangle Meshes. Presented at Mathematical Methods for Curves and Surfaces, Tonsberg, Norway

In this paper we measure the effects of noise on the performance of a standard entropy compression algorithm for quantized triangle meshes. In a first experiment, we show that a small amount of added noise may lead to slightly smaller filesizes. The... Read More about Effects of Noise on Quantized Triangle Meshes.

The value of mapping studies – A participant-observer case study (2010)
Presentation / Conference Contribution
Kitchenham, B. A., Budgen, D., & Brereton, O. P. (2010, January). The value of mapping studies – A participant-observer case study. Presented at 14th International Conference on Evaluation and Assessment in Software Engineering, EASE 2010, Durham University

Background: We are strong advocates of evidence-based software engineering (EBSE) in general and systematic literature reviews (SLRs) in particular. We believe it is essential that the SLR methodology is being used constructively to support software... Read More about The value of mapping studies – A participant-observer case study.