Outputs (78)

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.

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.

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.

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.

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.

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.

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.

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.