Publications of Igor Razgon
[J1] E. Hebrard, B. O'Sullivan, I. Razgon and D. Marx “Soft Constraints of Difference and Equality”,
Journal of Artificial Intelligence Research (JAIR), Volume 41, pp. 97-130, 2011. PDF
[J2] I. Razgon and B. O’Sullivan “Almost-2-SAT is Fixed-Parameter Tractable”,
Journal of Computer and System Sciences, Volume 75, Issue 8, pp. 435–450, 2009. PDF
[J3] I. Razgon “Faster Computation of Maximum Independent Set and Parameterized Vertex Cover for
Graphs with Maximum Degree 3”, Journal on Discrete Algorithms, Volume 7, pp. 191-212, 2009. PDF
[J4] D. Marx, and I. Razgon “Constant ratio fixed-parameter approximation of the edge multicut problem”,
“Information Processing Letters” journal, Volume 109, Issue 20, pp. 1161-1166, 2009. PDF
[J5] G. Gutin, I. Razgon, and E.-J. Kim, “Minimum Leaf Out-branching and Related Problems”,
Theoretical Computer Science, Volume 410, pp. 4571-4579, 2009. PDF
[J7] F. Fomin, S. Gaspers, A. Pyatkin, and I. Razgon “On the Minimum Feedback Vertex Set Problem:
Exact and Enumeration Algorithms”, Algorithmica, Volume 52, Issue 2, pp. 293-307, 2008. PDF
[J8] I. Razgon “A 2O(k)poly(n) Algorithm for the Parameterized Convex Recoloring Problem”,
[J9] I. Razgon and A. Meisels “A CSP Search Algorithm with Responsibility Sets and Kernels”,
"Constraints" journal, Volume 12, Issue 2, pp. 151-177, 2007. PDF
[P1] A. Atminas and V. Lozin and I. Razgon “Linear time algorithm for computing a small biclique in graphs
without long induced paths ”, SWAT 2012, to appear. PDF
[P2] D. Marx and I. Razgon “Fixed-parameter tractability of multicut parameterized by the size of
the cutset”, 43d Annual ACM Symposium on Theory of Computing (STOC 2011), pp. 469-478. PDF
[P3] D. Marx, B. O’Sullivan and I. Razgon “Treewidth reduction for constrained separation and
bipartization problems”, The 27th International Symposium on Theoretical Aspects of
Computer Science (STACS 2010), pp.561-572. PDF
[P4] E. Hebrard, D. Marx, B. O’Sullivan and I. Razgon “Constraints of Difference and Equality:
A Complete Taxonomic Characterisation”, The 15th International Conference on Principles and
Practice of Constraint Programming (CP 2009), pp.424-438. PDF
[P5] G. Gutin, D. Karapetyan and I. Razgon “FPT Algorithms in Analysis of Heuristics for
Extracting Networks in Linear Programs”, The 4th Internetional Workshop on Parametrized
and Exact Computation (IWPEC 2009), to appear. PDF
[P6] D. Marx, and I. Razgon “Constant ratio fixed-parameter approximation of the edge multicut problem”,
The 17th Annual European Symposium on Algorithms (ESA 2009), pp. 647-658.. PDF
[P7] D. Johannsen, I. Razgon, and M. Wahlström “Solving SAT for CNF Formulas with a
One-Sided Restriction on Variable Occurrences”, The 12th International Conference
on Theory and Applications of Satisfiability Testing (SAT 2009), pp. 80-85. PDF
[P8] E. Hebrard, B. O’Sullivan and I. Razgon “A Soft Constraint of Equality: Complexity and
Approximability”, The 14th International Conference on Principles and Practice of Constraint
Programming (CP 2008), pp.358-371. PDF
[P9] I. Razgon and B. O’Sullivan “Almost-2-SAT is Fixed-Parameter Tractable”, 35th International
[P10] J. Chen, Y. Liu, S. Lu, B. O’Sullivan, and I. Razgon
[P11] G. Gutin, I. Razgon, and E.-J. Kim, “Minimum Leaf Out-Branching Problems”,
the 4th International Conference on Algorithmic Aspects in Information and Management
(AAIM 2008), LNCS 5034, pp. 235–246. PDF
[P12] I. Razgon, B. O’Sullivan, and G. Provan “Generalizing Global Constraints Based on Network Flows”,
Volume "Recent Advances in Constraints 2007”, CSCLP 2007, LNAI 5129, pp. 112–126, 2008. PDF
[P13] I. Razgon “Parameterized DFVS and Multicut Problems on DAGs”, The Third Workshop on
Algorithms and Complexity in Durham (ACiD 2007), KCL Texts in Algorithmics, volume 9, pp. 119-128.
[P14] I. Razgon “Computing Minimum Directed Feedback Vertex Set in O*(1.9977n)”, The Tenth Italian
Conference on Theoretical Computer Science (ICTCS 2007), World Scientific, volume 6581, pp. 70-81. PDF
[P15] I. Razgon and B. O’Sullivan “Efficient Recognition of Acyclic Clustered Constraint Satisfaction Problems”,
Volume "Recent Advances in Constraints 2006”, LNAI 4651, pp. 154–168, 2007. PDF
[P16] B. Chor, M. Fellows, M. Ragan, I. Razgon, F. Rosamond, and S.Snir “Connected Coloring Competition
For General Graphs: Algorithms and Complexity”, The 13th Annual International Computing and
Combinatorics Conference (COCOON 2007), LNCS 4598, pp. 75-85. PDF
[P17] I. Razgon “A Faster Solving of the Maximum Independent Set Problem for Graphs with Maximal Degree 3”,
The Second Workshop on Algorithms and Complexity in Durham (ACiD 2006), PDF
KCL Texts in Algorithmics, volume 7, pages 131-142.
[P18] I. Razgon “Exact Computation of Maximum Induced Forest”, Scandinavian Workshop on Algorithm PDF
Theory (SWAT 2006), LNCS 4059, pp. 160-171.
[P19] I. Razgon and A. Meisels “A CSP Search Algorithm with Reduced Branching Factor”, PDF
Volume "Recent Advances in Constraints", LNAI 3978, pp. 59-72, 2006.
[P20] I. Razgon “Complexity Analysis of Heuristic CSP Search Algorithms”, Volume "Recent Advances PDF
in Constraints", LNAI 3978, pp. 88-99, 2006.
[P21] I. Razgon and A. Meisels “CSP Search with Responsibility Sets and Kernels”,
The International Joint Conference on Artificial Intelligence (IJCAI 2005), pp.1533-1534.
[P22] I. Razgon and A. Meisels “Pruning by Equally Constrained Variables”, LNAI 3419, pp.26-40, 2005.
[P23] I. Razgon and A. Meisels “Maintaining Dominance Consistency”, The 9th International Conference
on Principles and Practice of Constraint Programming (CP 2003), pp. 945-950.
[P24] I. Razgon and R. Brafman “A Forward Search Planning Algorithm with a Goal Ordering Heuristic”,
Proceedings of the 6-th European Conference on Planning (ECP 2001), pp.25-36.
[N1] I. Razgon “Partial kernelization of multiway cut: bounding the number of vertices with small excess”, PDF
The 21st International Workshop on Combinatorial Algorithms (IWOCA 2010).
[N2] I. Razgon, B. O`Sullivan, G. Provan “Generalizing Global Constraints Based on Network Flows”,
5-th Modelling and Reformulation Workshop collocated with CP 2006.
[N3] I. Razgon, B. O`Sullivan, G. Provan “Tree-structured Constraint Satisfaction Problems Revisited”,
The 11th Joint Annual Workshop of ERCIM / CoLogNet on Constraint Solving and Contraint
Logic Programming (CSCLP 2006).
[N4] I. Razgon and A. Meisels “A CSP Search Algorithm with Reduced Branching Factor”,
The 10th Joint Annual Workshop of ERCIM / CoLogNet on Constraint Solving and Constraint
Logic Programming (CSCLP 2005).
[N5] I. Razgon and A. Meisels “Pruning by the Use of Equally Constrained Variables”, CSCLP 2004,
The 9th Joint Annual Workshop of ERCIM / CoLogNet on Constraint Solving and Constraint
Logic Programming (CSCLP 2004), pp 215-230.
[N6] I. Razgon “Master-slave cooperation of complete constraint solvers”,
The 3th Workshop on Cooperative Solvers in Constraint Programming (CoSolv 2003).
[N7] I. Razgon “Nogood Learning for Classical Planning”, The Doctoral Consortium of
the International Conference on Automated Planning and Scheduling (ICAPS 2003).
[N8] I. Razgon and A. Meisels “Symmetry Breaking via Dominance Detection for Lookahead
Constraint Solvers”, The Second International Workshop on Symmetry in Constraint Satisfaction
Problems (SymCon 2002).
[N9] A. Meisels and I. Razgon “Distributed Forward Checking with Conflict Based Backjumping and
Dynamic Ordering”, Workshop on Cooperative Solvers in Constraint Programming (CoSolv 2002).
[N10] A. Meisels, E. Kaplansky, I. Razgon and R. Zivan “Comparing Performance of Distributed
Constraints Processing Algorithms”, Third International Workshop on Distributed Constraint
Reasoning, 2002.
[N11] A. Meisels and I. Razgon “Distributed Forward Checking with Dynamic Ordering”, Workshop on
Cooperative Solvers in Constraint Programming (CoSolv 2001).