Professor Daniel Paulusma's Outputs (15)

Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs (2009)
Presentation / Conference Contribution
Broersma, H. J., Fomin, F. V., Hof van 't, P., & Paulusma, D. (2009, June). Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs. Presented at 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Montpellier, France

The Hamiltonian Cycle problem asks if an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. So far, finding an exact algorithm that solves it in O *(α n ) time for some constant α< 2 is a no...

Induced packing of odd cycles in a planar graph (2009)
Presentation / Conference Contribution
Golovach, P. A., Kaminski, M., Paulusma, D., & Thilikos, D. M. (2009, December). Induced packing of odd cycles in a planar graph. Presented at 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, United States

Finding Induced Paths of Given Parity in Claw-Free Graphs (2009)
Presentation / Conference Contribution
Hof van 't, P., Kaminski, M., & Paulusma, D. (2009, December). Finding Induced Paths of Given Parity in Claw-Free Graphs. Presented at 35th International Workshop on Graph-Theoretic Concepts in Computer Science, Montpellier, France

The Parity Path problem is to decide if a given graph G contains both an odd length and an even length induced path between two specified vertices s and t. In the related problems Odd Induced Path and Even Induced Path, the goal is to determine wheth... Read More about Finding Induced Paths of Given Parity in Claw-Free Graphs.

On partitioning a graph into two connected subgraphs (2009)
Presentation / Conference Contribution
Paulusma, D., & Rooij van, J. M. M. (2009, December). On partitioning a graph into two connected subgraphs. Presented at 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, United States

Suppose a graph G is given with two vertex-disjoint sets of vertices Z₁ and Z₂. Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z₁ and Z₂, respectively? This problem is known... Read More about On partitioning a graph into two connected subgraphs.

Parameterizing cut sets in a graph by the number of their components (2009)
Presentation / Conference Contribution
Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. M. (2009, December). Parameterizing cut sets in a graph by the number of their components. Presented at 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, United States

For a connected graph G = (V,E), a subset U ⊆ V is called a k-cut if U disconnects G, and the subgraph induced by U contains exactly k ( ≥ 1) components. More specifically, a k-cut U is called a (k,ℓ)-cut if V \U induces a subgraph with exactly ℓ ( ≥... Read More about Parameterizing cut sets in a graph by the number of their components.

Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs (2009)
Journal Article
Broersma, H., Paulusma, D., & Yoshimoto, K. (2009). Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs. Graphs and Combinatorics, 25(4), 427-460. https://doi.org/10.1007/s00373-009-0855-7

Let G be a claw-free graph with order n and minimum degree δ. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If δ = 4, then G has a 2-factor with at most (5n − 14)/18 compo... Read More about Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs.

Three complexity results on coloring Pk-free graphs (2009)
Presentation / Conference Contribution
Broersma, H. J., Fomin, F. V., Golovach, P. A., & Paulusma, D. (2023, June). Three complexity results on coloring Pk-free graphs. Presented at 20th International Workshop on Combinatorial Algorithms (IWOCA 2009), Hradec nad Moravicí, Czech Republic

We prove three complexity results on vertex coloring problems restricted to Pk-free graphs, i.e., graphs that do not contain a path on k vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring rema... Read More about Three complexity results on coloring Pk-free graphs.

On the core and f-nucleolus of flow games (2009)
Journal Article
Kern, W., & Paulusma, D. (2009). On the core and f-nucleolus of flow games. Mathematics of Operations Research, 34(4), 981-991. https://doi.org/10.1287/moor.1090.0405

Using the ellipsoid method, both Deng et al. [Deng, X., Q. Fang, X. Sun. 2006. Finding nucleolus of flow game. Proc. 17th ACM-SIAM Sympos. Discrete Algorithms. ACM Press, New York, 124–131] and Potters et al. [Potters, J., H. Reijnierse, A. Biswas. 2... Read More about On the core and f-nucleolus of flow games.

λ-backbone colorings along pairwise disjoint stars and matchings (2009)
Journal Article
Broersma, H., Fujisawa, J., Marchal, L., Paulusma, D., Salman, A., & Yoshimoto, K. (2009). λ-backbone colorings along pairwise disjoint stars and matchings. Discrete Mathematics, 309(18), 5596-5609. https://doi.org/10.1016/j.disc.2008.04.007

Given an integer λ≥2, a graph G=(V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring of (G,H) is a proper vertex coloring V→{1,2,…} of G, in which the colors assigned to adjacent vertices in H differ by at least λ. We study... Read More about λ-backbone colorings along pairwise disjoint stars and matchings.

Computing role assignments of chordal graphs (2009)
Presentation / Conference Contribution
Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2009, September). Computing role assignments of chordal graphs. Presented at 17th International Symposium on Fundamentals of Computation Theory (FCT 2009), Wroclaw, Poland

In social network theory, a simple graph G is called k-role assignable if there is a surjective mapping that assigns a number from {1,...,k} called a role to each vertex of G such that any two vertices with the same role have the same sets of roles a... Read More about Computing role assignments of chordal graphs.

Partitioning graphs into connected parts (2009)
Presentation / Conference Contribution
Hof, P. V. '., Paulusma, D., & Woeginger, G. (2009, August). Partitioning graphs into connected parts. Presented at Fourth International Computer Science Symposium in Russia (CSR 2009)., Novosibirsk, Russia

The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing pre-specified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The Longest Pa... Read More about Partitioning graphs into connected parts.

Partitioning graphs into connected parts (2009)
Journal Article
Hof, P. V. '., Paulusma, D., & Woeginger, G. J. (2009). Partitioning graphs into connected parts. Theoretical Computer Science, 410(47-49), 4834-4843. https://doi.org/10.1016/j.tcs.2009.06.028

The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing prespecified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The Longest Pat... Read More about Partitioning graphs into connected parts.

Covering graphs with few complete bipartite subgraphs (2009)
Journal Article
Fleischner, H., Mujuni, E., Paulusma, D., & Szeider, S. (2009). Covering graphs with few complete bipartite subgraphs. Theoretical Computer Science, 410(21-23), 2045-2053. https://doi.org/10.1016/j.tcs.2008.12.059

We consider computational problems on covering graphs with bicliques (complete bipartite subgraphs). Given a graph and an integer k, the biclique cover problem asks whether the edge-set of the graph can be covered with at most k bicliques; the bicliq... Read More about Covering graphs with few complete bipartite subgraphs.

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number (2009)
Journal Article
Broersma, H., Marchal, L., Paulusma, D., & Salman, A. (2009). Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number. Discussiones Mathematicae. Graph Theory, 29(1), 143-162. https://doi.org/10.7151/dmgt.1437

We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a l-backbone coloring for G and H is a proper vertex col... Read More about Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number.

Upper bounds and algorithms for parallel knock-out numbers (2009)
Journal Article
Broersma, H., Johnson, M., & Paulusma, D. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science, 410(14), 1319-1327. https://doi.org/10.1016/j.tcs.2008.03.024

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the... Read More about Upper bounds and algorithms for parallel knock-out numbers.