Skip to main content

Research Repository

Advanced Search

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.

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems (2012)
Journal Article
Dantchev, S., & Martin, B. (2013). Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems. Computational Complexity, 22(1), 191-213. https://doi.org/10.1007/s00037-012-0049-1

We prove a dichotomy theorem for the rank of propositional contradictions, uniformly generated from first-order sentences, in both the Lovász-Schrijver (LS) and Sherali-Adams (SA) refutation systems. More precisely, we first show that the proposition... Read More about Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems.

Computing vertex-surjective homomorphisms to partially reflexive trees (2012)
Journal Article
Golovach, P., Paulusma, D., & Song, J. (2012). Computing vertex-surjective homomorphisms to partially reflexive trees. Theoretical Computer Science, 457, 86-100. https://doi.org/10.1016/j.tcs.2012.06.039

A homomorphism from a graph GG to a graph HH is a vertex mapping f:VG→VHf:VG→VH such that f(u)f(u) and f(v)f(v) form an edge in HH whenever uu and vv form an edge in GG. The HH-Coloring problem is that of testing whether a graph GG allows a homomorph... Read More about Computing vertex-surjective homomorphisms to partially reflexive trees.

Finding vertex-surjective graph homomorphisms (2012)
Journal Article
Golovach, P., Lidicky, B., Martin, B., & Paulusma, D. (2012). Finding vertex-surjective graph homomorphisms. Acta Informatica, 49(6), 381-394. https://doi.org/10.1007/s00236-012-0164-0

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.

On the parameterized complexity of coloring graphs in the absence of a linear forest (2012)
Journal Article
Couturier, J., Golovach, P., Kratsch, D., & Paulusma, D. (2012). On the parameterized complexity of coloring graphs in the absence of a linear forest. Journal of discrete algorithms, 15, 56-62. https://doi.org/10.1016/j.jda.2012.04.008

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 Listk-Coloring problem requires in addition that every vertex u must receive a color from some giv... Read More about On the parameterized complexity of coloring graphs in the absence of a linear forest.

Remoteness of permutation codes (2012)
Journal Article
Cameron, P. J., & Gadouleau, M. (2012). Remoteness of permutation codes. European Journal of Combinatorics, 33(6), 1273-1285. https://doi.org/10.1016/j.ejc.2012.03.027

In this paper, we introduce a new parameter of a code, referred to as the remoteness, which can be viewed as a dual to the covering radius. Indeed, the remoteness is the minimum radius needed for a single ball to cover all codewords. After giving som... Read More about Remoteness of permutation codes.

Cutting Planes and the Parameter Cutwidth (2012)
Journal Article
Dantchev, S., & Martin, B. (2012). Cutting Planes and the Parameter Cutwidth. Theory of Computing Systems, 51(1), 50-64. https://doi.org/10.1007/s00224-011-9373-0

We introduce the parameter cutwidth for the Cutting Planes (CP) system of Gomory and Chvátal. We provide linear lower bounds on cutwidth for two simple polytopes. Considering CP as a propositional refutation system, one can see that the cutwidth of a... Read More about Cutting Planes and the Parameter Cutwidth.

A simple polynomial algorithm for the longest path problem on cocomparability graphs (2012)
Journal Article
Mertzios, G., & Corneil, D. (2012). A simple polynomial algorithm for the longest path problem on cocomparability graphs. SIAM Journal on Discrete Mathematics, 26(3), 940-963. https://doi.org/10.1137/100793529

Given a graph $G$, the longest path problem asks to compute a simple path of $G$ with the largest number of vertices. This problem is the most natural optimization version of the well-known and well-studied Hamiltonian path problem, and thus it is NP... Read More about A simple polynomial algorithm for the longest path problem on cocomparability graphs.

Computing role assignments of proper interval graphs in polynomial time (2012)
Journal Article
Heggernes, P., van 't Hof, P., & Paulusma, D. (2012). Computing role assignments of proper interval graphs in polynomial time. Journal of discrete algorithms, 14, 173-188. https://doi.org/10.1016/j.jda.2011.12.004

An R-role assignment of a graph G is a locally surjective homomorphism from G to graph R. For a fixed graph R, the R-Role Assignment problem is to decide, for an input graph G, whether G has an R-role assignment. When both graphs G and R are given as... Read More about Computing role assignments of proper interval graphs in polynomial time.

The recognition of triangle graphs (2012)
Journal Article
Mertzios, G. (2012). The recognition of triangle graphs. Theoretical Computer Science, 438, 34-47. https://doi.org/10.1016/j.tcs.2012.02.042

Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L1 and L2 of the plane. This subclass of perfect graphs has received considerable attention as it generalizes i... Read More about The recognition of triangle graphs.

On graph contractions and induced minors (2012)
Journal Article
Hof, P. V. '., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. (2012). On graph contractions and induced minors. Discrete Applied Mathematics, 160(6), 799-809. https://doi.org/10.1016/j.dam.2010.05.005

The Induced Minor Containment problem takes as input two graphs G and H, and asks whether G has H as an induced minor. We show that this problem is fixed parameter tractable in |VH| if G belongs to any nontrivial minor-closed graph class and H is a p... Read More about On graph contractions and induced minors.

Distance three labelings of trees (2012)
Journal Article
Fiala, J., Golovach, P., Kratochvil, J., Lidický, B., & Paulusma, D. (2012). Distance three labelings of trees. Discrete Applied Mathematics, 160(6), 764-779. https://doi.org/10.1016/j.dam.2011.02.004

An L(2,1,1)-labeling of a graph G assigns nonnegative integers to the vertices of G in such a way that labels of adjacent vertices differ by at least two, while vertices that are at distance at most three are assigned different labels. The maximum la... Read More about Distance three labelings of trees.

Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time (2012)
Journal Article
Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2012). Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time. Theoretical Computer Science, 423, 1-10. https://doi.org/10.1016/j.tcs.2011.12.076

Let 2P3 denote the disjoint union of two paths on three vertices. A graph G that has no subgraph isomorphic to a graph H is called H-free. The Vertex Coloring problem is the problem to determine the chromatic number of a graph. Its computational comp... Read More about Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time.

Induced packing of odd cycles in planar graphs (2012)
Journal Article
Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. (2012). Induced packing of odd cycles in planar graphs. Theoretical Computer Science, 420, 28-35. https://doi.org/10.1016/j.tcs.2011.11.004

An induced packing of odd cycles in a graph is a packing such that there is no edge in the graph between any two odd cycles in the packing. We prove that an induced packing of k odd cycles in an n-vertex graph can be found (if it exists) in time 2O(k... Read More about Induced packing of odd cycles in planar graphs.

Rank Metric Decoder Architectures for Random Linear Network Coding with Error Control (2012)
Journal Article
Chen, N., Yan, Z., Gadouleau, M., Wang, Y., & Suter, B. W. (2012). Rank Metric Decoder Architectures for Random Linear Network Coding with Error Control. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 20(2), 296-309. https://doi.org/10.1109/tvlsi.2010.2096239

While random linear network coding is a powerful tool for disseminating information in communication networks, it is highly susceptible to errors caused by various sources. Due to error propagation, errors greatly deteriorate the throughput of networ... Read More about Rank Metric Decoder Architectures for Random Linear Network Coding with Error Control.

The k-in-a-path problem for claw-free graphs (2012)
Journal Article
Fiala, J., Kamiński, M., Lidický, B., & Paulusma, D. (2012). The k-in-a-path problem for claw-free graphs. Algorithmica, 62(1-2), 499-519. https://doi.org/10.1007/s00453-010-9468-z

The k-in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbit... Read More about The k-in-a-path problem for claw-free graphs.