Professor Daniel Paulusma's Outputs (311)

On disconnected cuts and separators (2011)
Journal Article
Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. (2011). On disconnected cuts and separators. Discrete Applied Mathematics, 159(13), 1345-1351. https://doi.org/10.1016/j.dam.2011.04.027

For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u∈U, the subgraph induced by (V∖U)∪{u} is connec... Read More about On disconnected cuts and separators.

On Finding Paths Passing through Specified Vertices (2011)
Report
Paulusma, D. (2011). On Finding Paths Passing through Specified Vertices. [No known commissioning body]

We consider undirected finite graphs that have no loops and no multiple edges. A graph is denoted G = (VG, EG), where VG is the set of vertices and EG is the set of edges. A graph containment problem is to decide whether one graph can be modified int... Read More about On Finding Paths Passing through Specified Vertices.

Computing Role Assignments of Proper Interval Graphs in Polynomial Time (2011)
Presentation / Conference Contribution
Heggernes, P., Hof, V. P., & Paulusma, D. (2011, December). Computing Role Assignments of Proper Interval Graphs in Polynomial Time. Presented at 21st International Workshop on Combinatorial Algorithms, IWOCA 2010, London

A homomorphism from a graph G to a graph R is locally surjective if its restriction to the neighborhood of each vertex of G is surjective. Such a homomorphism is also called an R-role assignment of G. Role assignments have applications in distributed... Read More about Computing Role Assignments of Proper Interval Graphs in Polynomial Time.

Satisfiability of acyclic and almost acyclic CNF formulas (II) (2011)
Presentation / Conference Contribution
Ordyniak, S., Paulusma, D., & Szeider, S. (2011, December). Satisfiability of acyclic and almost acyclic CNF formulas (II). Presented at 14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011, Ann Arbor, MI

In the first part of this work (FSTTCS’10) we have shown that the satisfiability of CNF formulas with β-acyclic hypergraphs can be decided in polynomial time. In this paper we continue and extend this work. The decision algorithm for β-acyclic formul... Read More about Satisfiability of acyclic and almost acyclic CNF formulas (II).

Contracting a chordal graph to a split graph or a tree (2011)
Presentation / Conference Contribution
Golovach, P. A., Kaminski, M., & Paulusma, D. (2011, December). Contracting a chordal graph to a split graph or a tree. Presented at 36th International Symposium on Mathematical Foundations of Computer Science 2011, MFCS 2011, Warsaw, Poland

The problems Contractibility and Induced Minor are to test whether a graph G contains a graph H as a contraction or as an induced minor, respectively. We show that these two problems can be solved in |VG|f(|VH|)VGf(VH) time if G is a chordal input gr... Read More about Contracting a chordal graph to a split graph or a tree.

The computational complexity of Disconnected Cut and 2K2-Partition (2011)
Presentation / Conference Contribution
Martin, B., & Paulusma, D. (2011, December). The computational complexity of Disconnected Cut and 2K2-Partition. Presented at Principles and Practice of Constraint Programming, 17th International Conference, CP 2011, Perugia, Italy

For a connected graph G = (V,E), a subset U ⊆ V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the problem to test whether a graph has a disconnected cut is NP-complete. Thi... Read More about The computational complexity of Disconnected Cut and 2K2-Partition.

List coloring in the absence of a linear forest (2011)
Presentation / Conference Contribution
Couturier, J. F., Golovach, P. A., Kratsch, D., & Paulusma, D. (2011, December). List coloring in the absence of a linear forest. Presented at 37th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2011, Tepla Monastery, Czech Republic

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The List k -Coloring problem requires in addition that every vertex u must receive a color from some g... Read More about List coloring in the absence of a linear forest.

Computing vertex-surjective homomorphisms to partially reflexive trees (2011)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & Song, J. (2011, December). Computing vertex-surjective homomorphisms to partially reflexive trees. Presented at 6th International Computer Science Symposium in Russia, CSR 2011., St Petersburg, Russia

Coloring graphs without short cycles and long induced paths (2011)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & Song, J. (2011, December). Coloring graphs without short cycles and long induced paths. Presented at Fundamentals of Computation Theory, 18th International Symposium, FCT 2011, Oslo, Norway

The girth of a graph G is the length of a shortest cycle in G. For any fixed girth g ≥ 4 we determine a lower bound ℓ(g) such that every graph with girth at least g and with no induced path on ℓ(g) vertices is 3-colorable. In contrast, we show the ex... Read More about Coloring graphs without short cycles and long induced paths.

Finding contractions and induced minors in chordal graphs via disjoint paths (2011)
Presentation / Conference Contribution
Belmonte, R., Golovach, P. A., Heggernes, P., Hof van 't, P., Kaminski, M., & Paulusma, D. (2011, December). Finding contractions and induced minors in chordal graphs via disjoint paths. Presented at 22nd International Symposium on Algorithms and Computation, ISAAC 2011, Yokohama, Japan

The k-Disjoint Paths problem, which takes as input a graph G and k pairs of specified vertices (s i ,t i ), asks whether G contains k mutually vertex-disjoint paths P i such that P i connects s i and t i , for i = 1,…,k. We study a natural variant of... Read More about Finding contractions and induced minors in chordal graphs via disjoint paths.

On Coloring Graphs without Induced Forests (2010)
Presentation / Conference Contribution
Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2010, December). On Coloring Graphs without Induced Forests. Presented at ISAAC 2010: Algorithms and Computation, Jeju Island, Korea

Narrowing Down the Gap on the Complexity of Coloring Pk-Free Graphs (2010)
Presentation / Conference Contribution
Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2010, June). Narrowing Down the Gap on the Complexity of Coloring Pk-Free Graphs. Presented at WG 2010: Graph-Theoretic Concepts in Computer Science, Zarós, Crete, Greece

Satisfiability of Acyclic and Almost Acyclic CNF Formulas (2010)
Presentation / Conference Contribution
Ordyniak, S., Paulusma, D., & Szeider, S. (2010, December). Satisfiability of Acyclic and Almost Acyclic CNF Formulas. Presented at IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), Chennai, India

Computing role assignments of chordal graphs (2010)
Journal Article
Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2010). Computing role assignments of chordal graphs. Theoretical Computer Science, 411(40-42), 3601-3613. https://doi.org/10.1016/j.tcs.2010.05.041

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.

Computing sharp 2-factors in claw-free graphs (2010)
Journal Article
Broersma, H., & Paulusma, D. (2010). Computing sharp 2-factors in claw-free graphs. Journal of discrete algorithms, 8(3), 321-329. https://doi.org/10.1016/j.jda.2009.07.001

In a previous paper we obtained an upper bound for the minimum number of components of a 2-factor in a claw-free graph. This bound is sharp in the sense that there exist infinitely many claw-free graphs for which the bound is tight. In this paper we... Read More about Computing sharp 2-factors in claw-free graphs.

Obtaining online ecological colourings by generalizing first-fit (2010)
Presentation / Conference Contribution
Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2010, December). Obtaining online ecological colourings by generalizing first-fit. Presented at 5th International Computer Science Symposium in Russia (CSR 2010), Kazan, Russia

A colouring of a graph is ecological if every pair of vertices that have the same set of colours in their neighbourhood are coloured alike. We consider the following problem: if a graph G and an ecological colouring c of G are given, can further vert... Read More about Obtaining online ecological colourings by generalizing first-fit.

Path factors and parallel knock-out schemes of almost claw-free graphs (2010)
Journal Article
Johnson, M., Paulusma, D., & Wood, C. (2010). Path factors and parallel knock-out schemes of almost claw-free graphs. Discrete Mathematics, 310(9), 1413-1423. https://doi.org/10.1016/j.disc.2009.04.022

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.

Comparing universal covers in polynomial time (2010)
Journal Article
Fiala, J., & Paulusma., D. (2010). Comparing universal covers in polynomial time. Theory of Computing Systems, 46(4), 620-635. https://doi.org/10.1007/s00224-009-9200-z

The universal cover T G of a connected graph G is the unique (possibly infinite) tree covering G, i.e., that allows a locally bijective homomorphism from T G to G. It is well-known that if a graph G covers a graph H, then their universal covers are i... Read More about Comparing universal covers in polynomial time.

A new characterization of P6-free graphs (2010)
Journal Article
Hof, P. V. '., & Paulusma, D. (2010). A new characterization of P6-free graphs. Discrete Applied Mathematics, 158(7), 731-740. https://doi.org/10.1016/j.dam.2008.08.025

We study P6-free graphs, i.e., graphs that do not contain an induced path on six vertices. Our main result is a new characterization of this graph class: a graph G is P6-free if and only if each connected induced subgraph of G on more than one vertex... Read More about A new characterization of P6-free 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.