We study algorithmic properties of the graph class $\mathrm{C}\mathrm{H}\mathrm{O}\mathrm{R}\mathrm{D}\mathrm{A}\mathrm{L}-ke$, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. It appears that a number of fundamental ...$\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}$${\mathrm{}}^{\mathcal{}\sqrt{}}{}^{\mathcal{}\mathrm{}}$$\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}$$\mathrm{}\mathrm{}\mathrm{}\mathrm{}\mathrm{}$

We consider subexponential algorithms finding weighted homomorphisms from intersection graphs of curves (string graphs) with n vertices to a fixed graph H. We provide a complete dichotomy: if H has no two vertices sharing two common ...

Planar graphs are known to allow subexponential algorithms running in time $$2^{O(\sqrt{n})}$$2O(n) or $$2^{O(\sqrt{n} \log n)}$$2O(nlogn) for most of the paradigmatic problems, while the brute-force time $$2^{\varTheta (n)}$$2?(n) is very likely to be ...

In algorithmic graph theory, a classic open question is to determine the complexity of the Maximum Independent Set problem on $$P_t$$Pt-free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are ...

In the Interval Completion problem we are given an n-vertex graph G and an integer k, and the task is to transform G by making use of at most k edge additions into an interval graph. This is a fundamental graph modification problem with applications in ...

We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to a wide range of geometric intersection graphs (intersections of similarly ...

We improve the running time of the general algorithmic technique known as Baker's approach (1994) [1] on H-minor-free graphs from O(n^f^(^|^H^|^)) to O(f(|H|)n^O^(^1^)). The numerous applications include, e.g. a 2-approximation for coloring and PTASes ...

Partial Cover problems are optimization versions of fundamental and well-studied problems like Vertex Cover and Dominating Set. Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number k of ...

The complexity status of the Maximum Independent Set Problem (MIS) for the family of P"5-free graphs is unknown. Although for many subclasses of P"5-free graphs MIS can be solved in polynomial time, only exponential time MIS-algorithms for general ...

New efficient algorithms for solving infinite-duration two-person adversary games with the decision problem inNP@?coNP, based on linear programming (LP), LP-representations, combinatorial LP, linear complementarity problem (LCP), controlled LP are ...

This paper has two purposes. The first is to present a new way to find a Steiner minimum tree (SMT) connectingN sites ind-space,d >- 2. We present (in Appendix 1) a computer code for this purpose. This is the only procedure known to the author for ...