25 citations · 97 across the 22 of their papers we have counts for
6 papers · 1 filter
Bin Packing with Linear Usage Costs
Hadrien Cambazard, Deepak Mehta, Barry O'Sullivan +1
Bin packing is a well studied problem involved in many applications. The classical bin packing problem is about minimising the number of bins and ignores how the bins are utilised.…
Finding small separators in linear time via treewidth reduction
Dániel Marx, Barry O'Sullivan, Igor Razgon
We present a method for reducing the treewidth of a graph while preserving all of its minimal separators up to a certain fixed size . This technique allows us to solve $s-…
Generating All Partitions: A Comparison Of Two Encodings
Jerome Kelleher, Barry O'Sullivan
Integer partitions may be encoded as either ascending or descending compositions for the purposes of systematic generation. Many algorithms exist to generate all descending composi…
Treewidth reduction for constrained separation and bipartization problems
Dániel Marx, Barry O'Sullivan, Igor Razgon
We present a method for reducing the treewidth of a graph while preserving all the minimal separators. This technique turns out to be very useful for establishing the fixed-p…
Almost 2-SAT is Fixed-Parameter Tractable
Igor Razgon, Barry O'Sullivan
We consider the following problem. Given a 2-CNF formula, is it possible to remove at most clauses so that the resulting 2-CNF formula is satisfiable? This problem is known to…
Directed Feedback Vertex Set is Fixed-Parameter Tractable
Igor Razgon, Barry O'Sullivan
We resolve positively a long standing open question regarding the fixed-parameter tractability of the parameterized Directed Feedback Vertex Set problem. In particular, we propose…