POPA , Alexandru

Recently, hardness results for problems in P were achieved using reasonable complexity theoretic assumptions such as the Strong Exponential Time Hypothesis. According to these assumptions, many graph theoretic problems do not admit truly subquadratic algorithms. A central technique used to tackle the difficulty of the above mentioned problems...

Recently, hardness results for problems in P were achieved using reasonable complexity theoretic assumptions such as the Strong Exponential Time Hypothesis. According to these assumptions, many graph theoretic problems do not admit truly subquadratic algorithms. A central technique used to tackle the difficulty of the above mentioned problems...

Parameterized complexity theory has enabled a refined classification of the difficulty of NP-hard optimization problems on graphs with respect to key structural properties, and so to a better understanding of their true difficulties. More recently, hardness results for problems in P were achieved using reasonable complexity theoretic...

A coloring of a graph G is properly connected if every two vertices of G are the ends of a properly colored path. We study the complexity of computing the proper connection number (minimum number of colors in a properly connected coloring) for edge and vertex colorings, in undirected and directed graphs, respectively. First we disprove some...

A properly connected coloring of a given graph G is one that ensures that every two vertices are the ends of a properly colored path. The proper connection number of G is the minimum number of colors in such a coloring. We study the proper connection number for edge and vertex colorings, in undirected and directed graphs, respectively. More...