papers
Publications (21)
cs.CC2015
On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
Igor Razgon
cs.DS2013
Fixed-parameter tractability of multicut parameterized by the size of the cutset
Dániel Marx, Igor Razgon
cs.DS2008
Almost 2-SAT is Fixed-Parameter Tractable
Igor Razgon, Barry O'Sullivan
cs.LO2014
On OBDDs for CNFs of bounded treewidth
Igor Razgon
math.CO2018
Linear read-once and related Boolean functions
Vadim Lozin, Igor Razgon, Viktor Zamaraev +2
cs.DM2015
Well-quasi-ordering does not imply bounded clique-width
Vadim Lozin, Igor Razgon, Viktor Zamaraev
cs.CC2016
Two types of branching programs with bounded repetition that cannot efficiently compute monotone 3-CNFs
Igor Razgon
cs.CC2017
Partial matching width and its application to lower bounds for branching programs
Igor Razgon
cs.DS2010
Treewidth reduction for constrained separation and bipartization problems
Dániel Marx, Barry O'Sullivan, Igor Razgon
math.CO2015
Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation
Aistis Atminas, Vadim V. Lozin, Igor Razgon
cs.CC2015
On the read-once property of branching programs and CNFs of bounded treewidth
Igor Razgon
cs.DM2011
Large Isolating Cuts Shrink the Multiway Cut
Igor Razgon
cs.LO2013
Cliquewidth and Knowledge Compilation
Igor Razgon, Justyna Petke
math.CO2017
Specifying a positive threshold function via extremal points
Vadim Lozin, Igor Razgon, Viktor Zamaraev +2
cs.AI2014
Soft Constraints of Difference and Equality
Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan +1
cs.DS2007
Directed Feedback Vertex Set is Fixed-Parameter Tractable
Igor Razgon, Barry O'Sullivan
cs.CC2016
Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs
Oded Lachish, Igor Razgon
cs.DS2010
Computing multiway cut within the given excess over the largest minimum isolating cut
Igor Razgon
cs.DS2011
Finding small separators in linear time via treewidth reduction
Dániel Marx, Barry O'Sullivan, Igor Razgon
cs.CC2014
No small nondeterministic read-once branching programs for CNFs of bounded treewidth
Igor Razgon
cs.AI2017
Non-FPT lower bounds for structural restrictions of decision DNNF
Andrea Calì, Florent Capelli, Igor Razgon