Outputs (38)

Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs (2013)
Book Chapter
Mertzios, G., & Spirakis, P. (2013). Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs. In P. V. E. Boas, F. C. Groen, G. F. Italiano, J. Nawrocki, & H. Sack (Eds.), SOFSEM 2013 : theory and practice of computer science : 39th international conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 26-31, 2013. Proceedings (332-343). Springer Verlag. https://doi.org/10.1007/978-3-642-35843-2_29

The 3-coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter 4. Moreover, assuming the Exponential Time Hypothesis (ETH), 3-coloring can not be solved i... Read More about Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs.

Strong Bounds for Evolution in Networks (2013)
Book Chapter
Mertzios, G., & Spirakis, P. (2013). Strong Bounds for Evolution in Networks. In F. V. Fomin, R. Freivalds, M. Kwiatkowska, & D. Peleg (Eds.), Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, proceedings, part II (669-680). Springer Verlag. https://doi.org/10.1007/978-3-642-39212-2_58

This work extends what is known so far for a basic model of evolutionary antagonism in undirected networks (graphs). More specifically, this work studies the generalized Moran process, as introduced by Lieberman, Hauert, and Nowak [Nature, 433:312-31... Read More about Strong Bounds for Evolution in Networks.

Temporal Network Optimization Subject to Connectivity Constraints (2013)
Book Chapter
Mertzios, G., Michail, O., Chatzigiannakis, I., & Spirakis, P. (2013). Temporal Network Optimization Subject to Connectivity Constraints. In F. V. Fomin, R. Freivalds, M. Kwiatkowska, & D. Peleg (Eds.), Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, proceedings, part II (657-668). Springer Verlag. https://doi.org/10.1007/978-3-642-39212-2_57

In this work we consider temporal networks, i.e. networks defined by a labeling λ assigning to each edge of an underlying graph G a set of discrete time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at w... Read More about Temporal Network Optimization Subject to Connectivity Constraints.

On the Recognition of Four-Directional Orthogonal Ray Graphs (2013)
Book Chapter
Felsner, S., Mertzios, G., & Mustata, I. (2013). On the Recognition of Four-Directional Orthogonal Ray Graphs. In K. Chatterjee, & J. Sgall (Eds.), Mathematical foundations of computer science 2013 : 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings (373-384). Springer Verlag. https://doi.org/10.1007/978-3-642-40313-2_34

Orthogonal ray graphs are the intersection graphs of horizontal and vertical rays (i.e. half-lines) in the plane. If the rays can have any possible orientation (left/right/up/down) then the graph is a 4-directional orthogonal ray graph (4-DORG). Othe... Read More about On the Recognition of Four-Directional Orthogonal Ray Graphs.

Distributing Storage in Cloud Environments (2013)
Presentation / Conference Contribution
Berenbrink, P., Brinkmann, A., Friedetzky, T., Meister, D., & Nagel, L. (2013, December). Distributing Storage in Cloud Environments. Presented at 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum

Closure Solvability for Network Coding and Secret Sharing (2013)
Journal Article
Gadouleau, M. (2013). Closure Solvability for Network Coding and Secret Sharing. IEEE Transactions on Information Theory, 59(12), 7858-7869. https://doi.org/10.1109/tit.2013.2282293

Network coding is a new technique to transmit data through a network by letting the intermediate nodes combine the packets they receive. Given a network, the network coding solvability problem decides whether all the packets requested by the destinat... Read More about Closure Solvability for Network Coding and Secret Sharing.

Relativization makes contradictions harder for Resolution (2013)
Journal Article
Dantchev, S., & Martin, B. (2014). Relativization makes contradictions harder for Resolution. Annals of Pure and Applied Logic, 165(3), 837-857. https://doi.org/10.1016/j.apal.2013.10.009

We provide a number of simplified and improved separations between pairs of Resolution-with-bounded-conjunction refutation systems, Res(d), as well as their tree-like versions, Res∗(d). The contradictions we use are natural combinatorial principles:... Read More about Relativization makes contradictions harder for Resolution.

Modifying a Graph Using Vertex Elimination (2013)
Journal Article
Golovach, P., Heggernes, P., Hof, V. '. P., Manne, F., Paulusma, D., & Pilipczuk, M. (2015). Modifying a Graph Using Vertex Elimination. Algorithmica, 72(1), 99-125. https://doi.org/10.1007/s00453-013-9848-2

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 Modifying a Graph Using Vertex Elimination.

Robust Satisfiability for CSPs: Hardness and Algorithmic Results (2013)
Journal Article
Dalmau, V., & Krokhin, A. (2013). Robust Satisfiability for CSPs: Hardness and Algorithmic Results. ACM Transactions on Computation Theory, 5(4), Article 15. https://doi.org/10.1145/2540090

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least a (1 − f(ε))-fraction of constraints for each (1 − ε)-satisfiable instance (i.e., such that at most a ε-fraction of constraints needs... Read More about Robust Satisfiability for CSPs: Hardness and Algorithmic Results.

The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial (2013)
Book Chapter
Mertzios, G. (2013). The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial. In H. L. Bodlaender, & G. F. Italiano (Eds.), Algorithms - ESA 2013 : 21st annual European symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings (719-730). Springer Verlag. https://doi.org/10.1007/978-3-642-40450-4_61

Intersection graphs of geometric objects have been extensively studied, both due to their interesting structure and their numerous applications; prominent examples include interval graphs and permutation graphs. In this paper we study a natural graph... Read More about The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial.

Characterizing graphs of small carving-width (2013)
Journal Article
Belmonte, R., Hof, V. '. P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Characterizing graphs of small carving-width. Discrete Applied Mathematics, 161(13-14), 1888-1893. https://doi.org/10.1016/j.dam.2013.02.036

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 immersio... Read More about Characterizing graphs of small carving-width.

On the fixation probability of superstars (2013)
Journal Article
Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2013). On the fixation probability of superstars. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 469(2156), https://doi.org/10.1098/rspa.2013.0193

The Moran process models the spread of genetic mutations through populations. A mutant with relative fitness r is introduced and the system evolves, either reaching fixation (an all-mutant population) or extinction (no mutants). In a widely cited pap... Read More about On the fixation probability of superstars.

Random walks which prefer unvisited edges : exploring high girth even degree expanders in linear time (2013)
Journal Article
Berenbrink, P., Cooper, C., & Friedetzky, T. (2015). Random walks which prefer unvisited edges : exploring high girth even degree expanders in linear time. Random Structures and Algorithms, 46(1), 36-54. https://doi.org/10.1002/rsa.20504

Let G = (V,E) be a connected graph with |V | = n vertices. A simple random walk on the vertex set of G is a process, which at each step moves from its current vertex position to a neighbouring vertex chosen uniformly at random. We consider a modified... Read More about Random walks which prefer unvisited edges : exploring high girth even degree expanders in linear time.

Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution (2013)
Journal Article
Bordewich, M., & Mihaescu, R. (2013). Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 10(3), 576-583. https://doi.org/10.1109/tcbb.2013.39

Distance-based phylogenetic methods attempt to reconstruct an accurate phylogenetic tree from an estimated matrix of pairwise distances between taxa. This paper examines two distance-based algorithms (GREEDYBME and FASTME) that are based on the princ... Read More about Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution.

Detecting induced minors in AT-free graphs (2013)
Journal Article
Golovach, P., Kratsch, D., & Paulusma, D. (2013). Detecting induced minors in AT-free graphs. Theoretical Computer Science, 482, 20-32. https://doi.org/10.1016/j.tcs.2013.02.029

The Induced Minor problem is that of testing whether a graph G can be modified into a graph H by a sequence of vertex deletions and edge contractions. If only edge contractions are permitted, we obtain the Contractibility problem. We prove that Induc... Read More about Detecting induced minors in AT-free graphs.

List Coloring in the Absence of a Linear Forest (2013)
Journal Article
Couturier, J., Golovach, P., Kratsch, D., & Paulusma, D. (2015). List Coloring in the Absence of a Linear Forest. Algorithmica, 71(1), 21-35. https://doi.org/10.1007/s00453-013-9777-0

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 List Coloring in the Absence of a Linear Forest.

Combinatorial Representations (2013)
Journal Article
Cameron, P. J., Gadouleau, M., & Riis, S. (2013). Combinatorial Representations. Journal of Combinatorial Theory, Series A, 120(3), 671-682. https://doi.org/10.1016/j.jcta.2012.12.002

This paper introduces combinatorial representations, which generalise the notion of linear representations of matroids. We show that any family of subsets of the same cardinality has a combinatorial representation via matrices. We then prove that any... Read More about Combinatorial Representations.

Increasing the minimum degree of a graph by contractions (2013)
Journal Article
Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Increasing the minimum degree of a graph by contractions. Theoretical Computer Science, 481, 74-84. https://doi.org/10.1016/j.tcs.2013.02.030

The Degree Contractibility problem is to test whether a given graph G can be modified to a graph of minimum degree at least d by using at most k contractions. We prove the following three results. First, Degree Contractibility is NP-complete even whe... Read More about Increasing the minimum degree of a graph by contractions.

Satisfiability of acyclic and almost acyclic CNF formulas (2013)
Journal Article
Ordyniak, S., Paulusma, D., & Szeider, S. (2013). Satisfiability of acyclic and almost acyclic CNF formulas. Theoretical Computer Science, 481, 85-99. https://doi.org/10.1016/j.tcs.2012.12.039

We show that the Satisfiability (SAT) problem for CNF formulas with ββ-acyclic hypergraphs can be solved in polynomial time by using a special type of Davis–Putnam resolution in which each resolvent is a subset of a parent clause. We extend this clas... Read More about Satisfiability of acyclic and almost acyclic CNF formulas.

Three complexity results on coloring Pk-free graphs (2013)
Journal Article
Broersma, H., Fomin, F., Golovach, P., & Paulusma, D. (2013). Three complexity results on coloring Pk-free graphs. European Journal of Combinatorics, 34(3), 609-619. https://doi.org/10.1016/j.ejc.2011.12.008

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