5 papers
Taming graphs with no large creatures and skinny ladders
Jakub Gajarský, Lars Jaffke, Paloma T. Lima +4
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class there exists a constant such that no member of $\mathcal{G}…
Subexponential-time algorithms for finding large induced sparse subgraphs
Jana Novotná, Karolina Okrasa, Michał Pilipczuk +3
Let and be hereditary graph classes. Consider the following problem: given a graph , find a largest, in terms of the number of vertices…
Duality Gap in Interval Linear Programming
Jana Novotná, Milan Hladík, Tomáš Masařík
This paper deals with the problem of linear programming with inexact data represented by real closed intervals. Optimization problems with interval data arise in practical computat…
On the Simultaneous Minimum Spanning Trees Problem
Matěj Konečný, Stanislav Kučera, Jana Novotná +4
Simultaneous Embedding with Fixed Edges (SEFE) is a problem where given planar graphs we ask whether they can be simultaneously embedded so that the embedding of each graph is…
Minimal Sum Labeling of Graphs
Matěj Konečný, Stanislav Kučera, Jana Novotná +3
A graph is called a sum graph if there is a so-called sum labeling of , i.e. an injective function such that for every it h…