Igor Razgon

According to our database, Igor Razgon authored at least 62 papers between 2003 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

The Treewidth and Pathwidth of Graph Unions.

Bogdan Alecu, Vadim V. Lozin, Daniel A. Quiroz, Roman Rabinovich, Igor Razgon, Viktor Zamaraev

SIAM J. Discret. Math., March, 2024

The splitting power of branching programs of bounded repetition and CNFs of bounded width.

Igor Razgon

Electron. Colloquium Comput. Complex., 2024

FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs.

Matthias Lanzinger, Igor Razgon

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

2023

Fractional covers of hypergraphs with bounded multi-intersection.

Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon

Theor. Comput. Sci., November, 2023

New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth.

Benjamin Bergougnoux, Tuukka Korhonen, Igor Razgon

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2023

2022

Tree-width dichotomy.

Vadim V. Lozin, Igor Razgon

Eur. J. Comb., 2022

FPT algoritms providing constant ratio approximation of hypertree width parameters for hypergraphs of bounded rank.

Igor Razgon

CoRR, 2022

2021

Complexity Analysis of Generalized and Fractional Hypertree Decompositions.

Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon

J. ACM, 2021

Classification of OBDD size for monotone 2-CNFs.

Igor Razgon

Electron. Colloquium Comput. Complex., 2021

2020

Complexity Analysis of General and Fractional Hypertree Decompositions.

Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon

CoRR, 2020

2019

Regular resolution for CNF of bounded incidence treewidth with few long clauses.

Andrea Calì, Igor Razgon

CoRR, 2019

2018

Well-quasi-ordering versus clique-width.

Vadim V. Lozin, Igor Razgon, Viktor Zamaraev

J. Comb. Theory B, 2018

Linear read-once and related Boolean functions.

Vadim V. Lozin, Igor Razgon, Viktor Zamaraev, Elena Zamaraeva, Nikolai Yu. Zolotykh

Discret. Appl. Math., 2018

2017

On Oblivious Branching Programs with Bounded Repetition that Cannot Efficiently Compute CNFs of Bounded Treewidth.

Igor Razgon

Theory Comput. Syst., 2017

Partial matching width and its application to lower bounds for branching programs.

Igor Razgon

CoRR, 2017

Non-FPT lower bounds for structural restrictions of decision DNNF.

Andrea Calì, Florent Capelli, Igor Razgon

CoRR, 2017

Querying the Deep Web: Back to the Foundations.

Andrea Calì, Davide Martinenghi, Igor Razgon, Martín Ugarte

Proceedings of the 11th Alberto Mendelzon International Workshop on Foundations of Data Management and the Web, 2017

Specifying a positive threshold function via extremal points.

Vadim V. Lozin, Igor Razgon, Viktor Zamaraev, Elena Zamaraeva, Nikolai Yu. Zolotykh

Proceedings of the International Conference on Algorithmic Learning Theory, 2017

2016

Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs.

Oded Lachish, Igor Razgon

CoRR, 2016

On the Read-Once Property of Branching Programs and CNFs of Bounded Treewidth.

Igor Razgon

Algorithmica, 2016

2015

Two types of branching programs with bounded repetition that cannot efficiently compute monotone 3-CNFs.

Igor Razgon

CoRR, 2015

Well-quasi-ordering Does Not Imply Bounded Clique-width.

Vadim V. Lozin, Igor Razgon, Victor Zamaraev

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2015

Quasipolynomial Simulation of DNNF by a Non-determinstic Read-Once Branching Program.

Igor Razgon

Proceedings of the Principles and Practice of Constraint Programming, 2015

2014

Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset.

Dániel Marx, Igor Razgon

SIAM J. Comput., 2014

Complexity of Conjunctive Query Answering under Access Limitations (Preliminary Report).

Andrea Calì, Igor Razgon

Proceedings of the 22nd Italian Symposium on Advanced Database Systems, 2014

On OBDDs for CNFs of Bounded Treewidth.

Igor Razgon

Proceedings of the Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, 2014

No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth.

Igor Razgon

Proceedings of the Parameterized and Exact Computation - 9th International Symposium, 2014

2013

Finding small separators in linear time via treewidth reduction.

Dániel Marx, Barry O'Sullivan, Igor Razgon

ACM Trans. Algorithms, 2013

Boundary Properties of Well-Quasi-Ordered Sets of Graphs.

Nicholas Korpelainen, Vadim V. Lozin, Igor Razgon

Order, 2013

Cliquewidth and Knowledge Compilation.

Igor Razgon, Justyna Petke

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2013, 2013

2012

Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths.

Aistis Atminas, Vadim V. Lozin, Igor Razgon

Proceedings of the Algorithm Theory - SWAT 2012, 2012

2011

Soft Constraints of Difference and Equality.

Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan, Igor Razgon

J. Artif. Intell. Res., 2011

Large Isolating Cuts Shrink the Multiway Cut

Igor Razgon

CoRR, 2011

2010

Computing multiway cut within the given excess over the largest minimum isolating cut

Igor Razgon

CoRR, 2010

Treewidth Reduction for Constrained Separation and Bipartization Problems.

Dániel Marx, Barry O'Sullivan, Igor Razgon

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

2009

Minimum leaf out-branching and related problems.

Gregory Z. Gutin, Igor Razgon, Eun Jung Kim

Theor. Comput. Sci., 2009

Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3.

Igor Razgon

J. Discrete Algorithms, 2009

Almost 2-SAT is fixed-parameter tractable.

Igor Razgon, Barry O'Sullivan

J. Comput. Syst. Sci., 2009

Constant ratio fixed-parameter approximation of the edge multicut problem.

Dániel Marx, Igor Razgon

Inf. Process. Lett., 2009

FPT Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs

Gregory Z. Gutin, Daniel Karapetyan, Igor Razgon

CoRR, 2009

Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences.

Daniel Johannsen, Igor Razgon, Magnus Wahlström

Proceedings of the Theory and Applications of Satisfiability Testing, 2009

Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs.

Gregory Z. Gutin, Daniel Karapetyan, Igor Razgon

Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

Constraints of Difference and Equality: A Complete Taxonomic Characterisation.

Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan, Igor Razgon

Proceedings of the Principles and Practice of Constraint Programming, 2009

2008

A fixed-parameter algorithm for the directed feedback vertex set problem.

Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon

J. ACM, 2008

On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms.

Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin, Igor Razgon

Algorithmica, 2008

Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract).

Igor Razgon, Barry O'Sullivan

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

A Soft Constraint of Equality: Complexity and Approximability.

Emmanuel Hebrard, Barry O'Sullivan, Igor Razgon

Proceedings of the Principles and Practice of Constraint Programming, 2008

Minimum Leaf Out-Branching Problems.

Gregory Z. Gutin, Igor Razgon, Eun Jung Kim

Proceedings of the Algorithmic Aspects in Information and Management, 2008

2007

A 2^O(k)poly(n) algorithm for the parameterized Convex Recoloring problem.

Igor Razgon

Inf. Process. Lett., 2007

A CSP Search Algorithm with Responsibility Sets and Kernels.

Igor Razgon, Amnon Meisels

Constraints An Int. J., 2007

Computing Minimum Directed Feedback Vertex Set in O(1.9977ⁿ).

Igor Razgon

Proceedings of the Theoretical Computer Science, 10th Italian Conference, 2007

Directed Feedback Vertex Set is Fixed-Parameter Tractable.

Igor Razgon, Barry O'Sullivan

Proceedings of the Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07., 2007

Generalizing Global Constraints Based on Network Flows.

Igor Razgon, Barry O'Sullivan, Gregory M. Provan

Proceedings of the Recent Advances in Constraints, 2007

Connected Coloring Completion for General Graphs: Algorithms and Complexity.

Benny Chor, Michael R. Fellows, Mark A. Ragan, Igor Razgon, Frances A. Rosamond, Sagi Snir

Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006

Exact Computation of Maximum Induced Forest.

Igor Razgon

Proceedings of the Algorithm Theory, 2006

Efficient Recognition of Acyclic Clustered Constraint Satisfaction Problems.

Igor Razgon, Barry O'Sullivan

Proceedings of the Recent Advances in Constraints, 2006

A Faster Solving of the Maximum Independent Set Problem for Graphs with Maximal Degree 3.

Igor Razgon

Proceedings of the Algorithms and Complexity in Durham 2006, 2006

2005

CSP Search with Responsibility Sets and Kernels.

Igor Razgon, Amnon Meisels

Proceedings of the IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30, 2005

A CSP Search Algorithm with Reduced Branching Factor.

Igor Razgon, Amnon Meisels

Proceedings of the Recent Advances in Constraints, 2005

Complexity Analysis of Heuristic CSP Search Algorithms.

Igor Razgon

Proceedings of the Recent Advances in Constraints, 2005

2004

Pruning by Equally Constrained Variables.

Igor Razgon, Amnon Meisels

Proceedings of the Recent Advances in Constraints, 2004

2003

Maintaining Dominance Consistency.

Igor Razgon, Amnon Meisels

Proceedings of the Principles and Practice of Constraint Programming, 2003