5 citations · 8 across the 3 of their papers we have counts for
4 papers
Proportionally dense subgraph of maximum size: complexity and approximation
Cristina Bazgan, Janka Chlebíková, Clément Dallard +1
We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in th…
Colourful components in -caterpillars and planar graphs
Janka Chlebíková, Clément Dallard
A connected component of a vertex-coloured graph is said to be colourful if all its vertices have different colours. By extension, a graph is colourful if all its connected compone…
Graphs without a partition into two proportionally dense subgraphs
Cristina Bazgan, Janka Chlebíková, Clément Dallard
A \emph{proportionally dense subgraph} (PDS) is an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the s…
The Firefighter Problem: A Structural Analysis
Janka Chlebíková, Morgan Chopin
We consider the complexity of the firefighter problem where b>=1 firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most th…