Outputs (82)

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.

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.

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

The Recognition of Triangle Graphs (2011)
Presentation / Conference Contribution
Mertzios, G. (2011, December). The Recognition of Triangle Graphs. Presented at 28th International Symposium on Theoretical Aspects of Computer Science (STACS), Dortmund, Germany

Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L_{1} and L_{2} of the plane. Strictly between permutation and trapezoid graphs lie the simple-triangle graphs... Read More about The Recognition of Triangle Graphs.

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.

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.

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).

Augmented k-ary n-cubes (2011)
Journal Article
Xiang, Y., & Stewart, I. (2011). Augmented k-ary n-cubes. Information Sciences, 181(1), 239-256. https://doi.org/10.1016/j.ins.2010.09.005

We define an interconnection network AQn,k which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmen... Read More about Augmented k-ary n-cubes.

Randomized Diffusion for Indivisible Loads (2011)
Presentation / Conference Contribution
Berenbrink, P., Cooper, C., Friedetzky, T., Friedrich, T., & Sauerwald, T. (2011, January). Randomized Diffusion for Indivisible Loads. Presented at Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms., San Francisco

We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tok... Read More about Randomized Diffusion for Indivisible Loads.

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.