Igor Razgon

Publication Activity (10 Years)

Years Active: 2003-2024
Publications (10 Years): 35

Top Topics

Query Answering

Bounded Treewidth

Independent Set

Boolean Functions

Top Venues

Publications

Bogdan Alecu, Vadim V. Lozin, Daniel A. Quiroz, Roman Rabinovich, Igor Razgon, Viktor Zamaraev
The Treewidth and Pathwidth of Graph Unions. SIAM J. Discret. Math. 38 (1) (2024)
Matthias Lanzinger, Igor Razgon
FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs. STACS (2024)
Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon
Fractional covers of hypergraphs with bounded multi-intersection. Theor. Comput. Sci. 979 (2023)
Benjamin Bergougnoux, Tuukka Korhonen, Igor Razgon
New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth. WG (2023)
Matthias Lanzinger, Igor Razgon
FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs. CoRR (2023)
Benjamin Bergougnoux, Tuukka Korhonen, Igor Razgon
New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth. CoRR (2023)
Igor Razgon
FPT algoritms providing constant ratio approximation of hypertree width parameters for hypergraphs of bounded rank. CoRR (2022)
Bogdan Alecu, Vadim V. Lozin, Daniel A. Quiroz, Roman Rabinovich, Igor Razgon, Viktor Zamaraev
The treewidth and pathwidth of graph unions. CoRR (2022)
Igor Razgon
The splitting power of branching programs of bounded repetition and CNFs of bounded width. CoRR (2022)
Vadim V. Lozin, Igor Razgon
Tree-width dichotomy. Eur. J. Comb. 103 (2022)
Igor Razgon
Classification of OBDD size for monotone 2-CNFs. Electron. Colloquium Comput. Complex. 28 (2021)
Igor Razgon
Classification of OBDD size for monotone 2-CNFs. CoRR (2021)
Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon
Complexity Analysis of Generalized and Fractional Hypertree Decompositions. J. ACM 68 (5) (2021)
Igor Razgon
Classification of OBDD Size for Monotone 2-CNFs. IPEC (2021)
Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon
Complexity Analysis of General and Fractional Hypertree Decompositions. CoRR (2020)
Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon
Fractional Covers of Hypergraphs with Bounded Multi-Intersection. MFCS (2020)
Vadim V. Lozin, Igor Razgon
Tree-width dichotomy. CoRR (2020)
Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon
Fractional Covers of Hypergraphs with Bounded Multi-Intersection. CoRR (2020)
Andrea Calì, Igor Razgon
Regular resolution for CNF of bounded incidence treewidth with few long clauses. CoRR (2019)
Vadim V. Lozin, Igor Razgon, Viktor Zamaraev, Elena Zamaraeva, Nikolai Yu. Zolotykh
Linear read-once and related Boolean functions. CoRR (2018)
Vadim V. Lozin, Igor Razgon, Viktor Zamaraev, Elena Zamaraeva, Nikolai Yu. Zolotykh
Linear read-once and related Boolean functions. Discret. Appl. Math. 250 (2018)
Vadim V. Lozin, Igor Razgon, Viktor Zamaraev
Well-quasi-ordering versus clique-width. J. Comb. Theory, Ser. B 130 (2018)
Vadim V. Lozin, Igor Razgon, Victor Zamaraev, Elena Zamaraeva, Nikolai Yu. Zolotykh
Specifying a positive threshold function via extremal points. CoRR (2017)
Andrea Calì, Florent Capelli, Igor Razgon
Non-FPT lower bounds for structural restrictions of decision DNNF. CoRR (2017)
Igor Razgon
On Oblivious Branching Programs with Bounded Repetition that Cannot Efficiently Compute CNFs of Bounded Treewidth. Theory Comput. Syst. 61 (3) (2017)
Andrea Calì, Davide Martinenghi, Igor Razgon, Martín Ugarte
Querying the Deep Web: Back to the Foundations. AMW (2017)
Igor Razgon
Partial matching width and its application to lower bounds for branching programs. CoRR (2017)
Vadim V. Lozin, Igor Razgon, Viktor Zamaraev, Elena Zamaraeva, Nikolai Yu. Zolotykh
Specifying a positive threshold function via extremal points. ALT (2017)
Igor Razgon
On the Read-Once Property of Branching Programs and CNFs of Bounded Treewidth. Algorithmica 75 (2) (2016)
Oded Lachish, Igor Razgon
Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs. CoRR (2016)
Igor Razgon
On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth. CoRR (2015)
Igor Razgon
Two types of branching programs with bounded repetition that cannot efficiently compute monotone 3-CNFs. CoRR (2015)
Igor Razgon
Quasipolynomial Simulation of DNNF by a Non-determinstic Read-Once Branching Program. CP (2015)
Vadim V. Lozin, Igor Razgon, Victor Zamaraev
Well-quasi-ordering Does Not Imply Bounded Clique-width. WG (2015)
Vadim V. Lozin, Igor Razgon, Victor Zamaraev
Well-quasi-ordering does not imply bounded clique-width. CoRR (2015)
Igor Razgon
No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth. IPEC (2014)
Igor Razgon
On the read-once property of branching programs and CNFs of bounded treewidth. CoRR (2014)
Dániel Marx, Igor Razgon
Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset. SIAM J. Comput. 43 (2) (2014)
Igor Razgon
On OBDDs for CNFs of Bounded Treewidth. KR (2014)
Igor Razgon
No small nondeterministic read-once branching programs for CNFs of bounded treewidth. CoRR (2014)
Andrea Calì, Igor Razgon
Complexity of Conjunctive Query Answering under Access Limitations (Preliminary Report). SEBD (2014)
Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan, Igor Razgon
Soft Constraints of Difference and Equality. CoRR (2014)
Igor Razgon
On OBDDs for CNFs of bounded treewidth. CoRR (2013)
Igor Razgon, Justyna Petke
Cliquewidth and Knowledge Compilation CoRR (2013)
Igor Razgon, Justyna Petke
Cliquewidth and Knowledge Compilation. SAT (2013)
Dániel Marx, Barry O'Sullivan, Igor Razgon
Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9 (4) (2013)
Nicholas Korpelainen, Vadim V. Lozin, Igor Razgon
Boundary Properties of Well-Quasi-Ordered Sets of Graphs. Order 30 (3) (2013)
Aistis Atminas, Vadim V. Lozin, Igor Razgon
Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths. SWAT (2012)
Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan, Igor Razgon
Soft Constraints of Difference and Equality. J. Artif. Intell. Res. 41 (2011)
Dániel Marx, Barry O'Sullivan, Igor Razgon
Finding small separators in linear time via treewidth reduction CoRR (2011)
Dániel Marx, Igor Razgon
Fixed-parameter tractability of multicut parameterized by the size of the cutset. STOC (2011)
Igor Razgon
Large Isolating Cuts Shrink the Multiway Cut CoRR (2011)
Dániel Marx, Igor Razgon
Fixed-parameter tractability of multicut parameterized by the size of the cutset CoRR (2010)
Igor Razgon
Computing multiway cut within the given excess over the largest minimum isolating cut CoRR (2010)
Dániel Marx, Barry O'Sullivan, Igor Razgon
Treewidth Reduction for Constrained Separation and Bipartization Problems. STACS (2010)
Igor Razgon
Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3. J. Discrete Algorithms 7 (2) (2009)
Dániel Marx, Barry O'Sullivan, Igor Razgon
Treewidth reduction for constrained separation and bipartization problems CoRR (2009)
Gregory Z. Gutin, Daniel Karapetyan, Igor Razgon
FPT Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs CoRR (2009)
Dániel Marx, Igor Razgon
Constant ratio fixed-parameter approximation of the edge multicut problem. Inf. Process. Lett. 109 (20) (2009)
Dániel Marx, Igor Razgon
Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem. ESA (2009)
Gregory Z. Gutin, Igor Razgon, Eun Jung Kim
Minimum leaf out-branching and related problems. Theor. Comput. Sci. 410 (45) (2009)
Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan, Igor Razgon
Constraints of Difference and Equality: A Complete Taxonomic Characterisation. CP (2009)
Daniel Johannsen, Igor Razgon, Magnus Wahlström
Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences. SAT (2009)
Igor Razgon, Barry O'Sullivan
Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci. 75 (8) (2009)
Gregory Z. Gutin, Daniel Karapetyan, Igor Razgon
Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs. IWPEC (2009)
Gregory Z. Gutin, Igor Razgon, Eun Jung Kim
Minimum Leaf Out-Branching Problems. AAIM (2008)
Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon
A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55 (5) (2008)
Gregory Z. Gutin, Eun Jung Kim, Igor Razgon
Minimum Leaf Out-Branching Problems CoRR (2008)
Igor Razgon, Barry O'Sullivan
Almost 2-SAT is Fixed-Parameter Tractable CoRR (2008)
Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin, Igor Razgon
On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms. Algorithmica 52 (2) (2008)
Igor Razgon, Barry O'Sullivan
Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract). ICALP (1) (2008)
Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon
A fixed-parameter algorithm for the directed feedback vertex set problem. STOC (2008)
Emmanuel Hebrard, Barry O'Sullivan, Igor Razgon
A Soft Constraint of Equality: Complexity and Approximability. CP (2008)
Igor Razgon
poly(n) algorithm for the parameterized Convex Recoloring problem. Inf. Process. Lett. 104 (2) (2007)
Igor Razgon, Barry O'Sullivan
Directed Feedback Vertex Set is Fixed-Parameter Tractable. Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)
Igor Razgon, Barry O'Sullivan
Directed Feedback Vertex Set is Fixed-Parameter Tractable CoRR (2007)
Igor Razgon
). ICTCS (2007)
Igor Razgon, Barry O'Sullivan, Gregory M. Provan
Generalizing Global Constraints Based on Network Flows. CSCLP (2007)
Igor Razgon, Amnon Meisels
A CSP Search Algorithm with Responsibility Sets and Kernels. Constraints An Int. J. 12 (2) (2007)
Benny Chor, Michael R. Fellows, Mark A. Ragan, Igor Razgon, Frances A. Rosamond, Sagi Snir
Connected Coloring Completion for General Graphs: Algorithms and Complexity. COCOON (2007)
Igor Razgon, Barry O'Sullivan
Efficient Recognition of Acyclic Clustered Constraint Satisfaction Problems. CSCLP (2006)
Igor Razgon
Exact Computation of Maximum Induced Forest. SWAT (2006)
Igor Razgon
A Faster Solving of the Maximum Independent Set Problem for Graphs with Maximal Degree 3. ACiD (2006)
Igor Razgon, Amnon Meisels
CSP Search with Responsibility Sets and Kernels. IJCAI (2005)
Igor Razgon, Amnon Meisels
A CSP Search Algorithm with Reduced Branching Factor. CSCLP (2005)
Igor Razgon
Complexity Analysis of Heuristic CSP Search Algorithms. CSCLP (2005)
Igor Razgon, Amnon Meisels
Pruning by Equally Constrained Variables. CSCLP (2004)
Igor Razgon, Amnon Meisels
Maintaining Dominance Consistency. CP (2003)