Outputs (75)

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.

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.

Path factors and parallel knock-out schemes of almost claw-free graphs (2010)
Presentation / Conference Contribution
Johnson, M., Paulusma, D., & Wood, C. (2010, December). Path factors and parallel knock-out schemes of almost claw-free graphs. Presented at 19th International Workshop on Combinatorial Algorithms, Nagoya

An H1, {H2}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H1 and all other components (if there are any) isomorphic to the graph H2.We completely characterise the class of connected almost claw-fre... Read More about Path factors and parallel knock-out schemes of almost claw-free graphs.