14 citations · 36 across the 8 of their papers we have counts for
11 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}…
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
Konrad Majewski, Tomáš Masařík, Jana Novotná +4
We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw as an induced subgraph [Chudnovsky, Pilipczuk, Pilip…
List Locally Surjective Homomorphisms in Hereditary Graph Classes
Pavel Dvořák, Monika Krawczyk, Tomáš Masařík +3
A locally surjective homomorphism from a graph to a graph is an edge-preserving mapping from to that is surjective in the neighborhood of each vertex in .…
Robust Connectivity of Graphs on Surfaces
Peter Bradshaw, Tomáš Masařík, Jana Novotná +1
Let denote the set of leaves in a tree . One natural problem is to look for a spanning tree of a given graph such that is as large as possible. This proble…
Clique-Width: Harnessing the Power of Atoms
Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná +2
Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph…
U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
Jan Kratochvíl, Tomáš Masařík, Jana Novotná
Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, the…
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…
Colouring -Free Graphs
Tereza Klimošová, Josef Malík, Tomáš Masařík +3
The -Colouring problem is to decide if the vertices of a graph can be coloured with at most colours for a fixed integer such that no two adjacent vertices are coloured a…
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…