Skip to main content

Research Repository

Advanced Search

Induced disjoint paths in AT-free graphs (2012)
Conference Proceeding
Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2012). Induced disjoint paths in AT-free graphs. In F. V. Fomin, & P. Kaski (Eds.), Algorithm Theory : 13th Scandinavian Symposium and Workshops, SWAT 2012, Helsinki, Finland, 4-6 July 2012 ; proceedings (153-164). https://doi.org/10.1007/978-3-642-31155-0_14

Paths P1,…,Pk in a graph G = (V,E) are said to be mutually induced if for any 1 ≤ i 

Induced disjoint paths in claw-free graphs (2012)
Conference Proceeding
Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2012). Induced disjoint paths in claw-free graphs. In L. Epstein, & P. Ferragina (Eds.), Algorithms, 20th Annual European Symposium, ESA 2012, Ljubljana, Slovenia, 10-12 September 2012 ; proceedings (515-526). https://doi.org/10.1007/978-3-642-33090-2_45

Paths P1,…,Pk in a graph G = (V,E) are said to be mutually induced if for any 1 ≤ i 

Closing complexity gaps for coloring problems on H-free graphs (2012)
Conference Proceeding
Golovach, P. A., Paulusma, D., & Song, J. (2012). Closing complexity gaps for coloring problems on H-free graphs. In K. Chao, T. Hsu, & D. Lee (Eds.), Algorithms and computation : 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, 19-21 December 2012 ; proceedings (14-23). https://doi.org/10.1007/978-3-642-35261-4_5

If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G = (V,E) is a mapping c: V → {1,2,…} such that no two adjacent vertices have the same color, i.e., c(u) ≠ c(v) if uv ∈ E; if |c(V)| ≤ k then... Read More about Closing complexity gaps for coloring problems on H-free graphs.

Finding vertex-surjective graph homomorphisms (2012)
Conference Proceeding
Golovach, P. A., Lidicky, B., Martin, B., & Paulusma, D. (2012). Finding vertex-surjective graph homomorphisms. In E. A. Hirsch, J. Karhumäki, A. Lepistö, & M. Prilutskii (Eds.), Computer science : theory and applications : 7th International Computer Science Symposium in Russia, CSR 2012, 3-7 July 2012, Nizhny Novgorod, Russia ; proceedings (160-171). https://doi.org/10.1007/978-3-642-30642-6_16

The Surjective Homomorphism problem is to test whether a given graph G called the guest graph allows a vertex-surjective homomorphism to some other given graph H called the host graph. The bijective and injective homomorphism problems can be formulat... Read More about Finding vertex-surjective graph homomorphisms.

Detecting induced minors in AT-free graphs (2012)
Conference Proceeding
Golovach, P. A., Kratsch, D., & Paulusma, D. (2012). Detecting induced minors in AT-free graphs. In K. Chao, T. Hsu, & D. Lee (Eds.), Algorithms and computation : 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, 19-21 December 2012 ; proceedings (495-505). https://doi.org/10.1007/978-3-642-35261-4_52

The problem Induced Minor is to test whether a graph G can be modified into a graph H by a sequence of vertex deletions and edge contractions. We prove that Induced Minor is polynomial-time solvable when G is AT-free, and H is fixed, i.e., not part o... Read More about Detecting induced minors in AT-free graphs.

Characterizing graphs of small carving-width (2012)
Conference Proceeding
Belmonte, R., van 't Hof, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2012). Characterizing graphs of small carving-width. In G. Lin (Ed.), Combinatorial optimization and applications : 6th International Conference, COCOA 2012, 5-9 August 2012, Banff, AB, Canada ; proceedings (360-370). https://doi.org/10.1007/978-3-642-31770-5_32

We characterize all graphs that have carving-width at most k for k = 1,2,3. In particular, we show that a graph has carving-width at most 3 if and only if it has maximum degree at most 3 and treewidth at most 2. This enables us to identify the immers... Read More about Characterizing graphs of small carving-width.

How to eliminate a graph (2012)
Conference Proceeding
Golovach, P., Heggernes, P., van 't Hof, P., Manne, F., Paulusma, D., & Pilipczuk, M. (2012). How to eliminate a graph. In M. C. Golumbic, M. Stern, A. Levy, & G. Morgenstern (Eds.), Graph-theoretic concepts in computer science: 38th international workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, revised selected papers (320-331). https://doi.org/10.1007/978-3-642-34611-8_32

Vertex elimination is a graph operation that turns the neighborhood of a vertex into a clique and removes the vertex itself. It has widely known applications within sparse matrix computations. We define the Elimination problem as follows: given two g... Read More about How to eliminate a graph.

4-Coloring H-free graphs when H is small (2012)
Conference Proceeding
Golovach, P., Paulusma, D., & Song, J. (2012). 4-Coloring H-free graphs when H is small. In M. Bieliková, G. Friedrich, G. Gottlob, S. Katzenbeisser, & G. Turán (Eds.), Theory and practice of computer science : 38th Conference on Current trends in theory and practice of computer science, SOFSEM 2012, Špindlerův Mlýn, Czech Republic, 21-27 January 2012 ; proceedings (289-300). https://doi.org/10.1007/978-3-642-27660-6_24

The k-Coloring problem is to test whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. If a graph G does not contain a graph H as an induced subgraph, then G is called H-free. For any fixed g... Read More about 4-Coloring H-free graphs when H is small.

Coloring graphs characterized by a forbidden subgraph (2012)
Conference Proceeding
Golovach, P. A., Paulusma, D., & Ries, B. (2012). Coloring graphs characterized by a forbidden subgraph. In B. Rovan, V. Sassone, & P. Widmayer (Eds.), Mathematical foundations of computer science 2012 : 37th International Symposium, MFCS 2012, Bratislava, Slovakia, 27-31 August 2012 ; proceedings (443-454). https://doi.org/10.1007/978-3-642-32589-2_40

The Coloring problem is to test whether a given graph can be colored with at most k colors for some given k, such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H as an in... Read More about Coloring graphs characterized by a forbidden subgraph.

Solutions for the stable rommates problem with payments (2012)
Conference Proceeding
Biró, P., Bomhoff, M., Golovach, P. A., Kern, W., & Paulusma, D. (2012). Solutions for the stable rommates problem with payments. In M. C. Golumbic, M. Stern, A. Levy, & G. Morgenstern (Eds.), Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, 26-28 June 2012 ; revised selected papers (69-80). https://doi.org/10.1007/978-3-642-34611-8_10

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

Obtaining planarity by contracting few edges (2012)
Conference Proceeding
Golovach, P. A., van 't Hog, P., & Paulusma, D. (2012). Obtaining planarity by contracting few edges. In B. Rovan, V. Sassone, & P. Widmayer (Eds.), Mathematical foundations of computer science 2012 : 37th international symposium, MFCS 2012, Bratislava, Slovakia, 27-31 August 2012 ; proceedings (455-466). https://doi.org/10.1007/978-3-642-32589-2_41

The Planar Contraction problem is to test whether a given graph can be made planar by using at most k edge contractions. This problem is known to be NP-complete. We show that it is fixed-parameter tractable when parameterized by k.

Placing regenerators in optical networks to satisfy multiple sets of requests (2012)
Journal Article
Mertzios, G., Sau, I., Shalom, M., & Zaks, S. (2012). Placing regenerators in optical networks to satisfy multiple sets of requests. IEEE/ACM Transactions on Networking, 20(6), 1870-1879. https://doi.org/10.1109/tnet.2012.2186462

The placement of regenerators in optical networks has become an active area of research during the last few years. Given a set of lightpaths in a network $G$ and a positive integer $d$ , regenerators must be placed in such a way that in any lightpath... Read More about Placing regenerators in optical networks to satisfy multiple sets of requests.

Detecting induced star-like minors in polynomial time (2012)
Journal Article
Fiala, J., Kaminksi, M., & Paulusma, D. (2012). Detecting induced star-like minors in polynomial time. Journal of discrete algorithms, 17, 74-85. https://doi.org/10.1016/j.jda.2012.11.002

The Induced Minor problem is to test whether a graph G contains a graph H as an induced minor, i.e., if G can be modified into H by a sequence of vertex deletions and edge contractions. When H is fixed, i.e., not part of the input, this problem is de... Read More about Detecting induced star-like minors in polynomial time.

Approximating Fixation Probabilities in the Generalized Moran Process (2012)
Conference Proceeding
Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2012). Approximating Fixation Probabilities in the Generalized Moran Process. In Y. Rabani (Ed.), Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan, January 17-19, 2012 (954-960). https://doi.org/10.1137/1.9781611973099.76

We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (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 pr... Read More about Approximating Fixation Probabilities in the Generalized Moran Process.