Home
# Dr. Igor Razgon's homepage (mobile version)

- I. Razgon "Quasipolynomial simulation of DNNF by a non-determinstic read-once branching program", The 21st International Conference on Principles and Practice of Constraint Programming (CP 2015), pp.367-375.
- V. Lozin , I. Razgon, and V. Zamaraev "Well-quasi-ordering does not imply bounded cliquewidth", The 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), to appear.
- I. Razgon "No small non-deterministic read-once branching programs for CNFs of bounded treewidth", The 9th International Symposium on Parameterized and Exact Computation (IPEC 2014), pp. 319-331.
- I. Razgon "On OBDDs for CNFs of bounded treewidth", The 14th International conference on Principles of Knowledge Representation and Reasoning (KR 2014).
- A. Cali and I. Razgon "Complexity of Conjunctive Query Answering under Access Limitations (Preliminary Report)", The 22-nd Italian Symposium on Advanced Database Systems (SEBD 2014), pp.256-263.
- I. Razgon and J. Petke "Cliquewidth and Knowledge Compilation", The 16th International Conference on Theory and Applications of Satisfiability Testing (SAT 2013), pp.335-350.
- A. Atminas, V. Lozin and I. Razgon "Linear time algorithm for computing a small biclique in graphs without long induced paths", The 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), pp.142-152.
- 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.
- 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.
- 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.
- G. Gutin, D. Karapetyan, and I. Razgon "Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs", The 4th Internetional Workshop on Parametrized and Exact Computation (IWPEC 2009), pp. 222-233.
- D. Marx, and I. Razgon Constant ratio fixed-parameter approximation of the edge multicut problem", The 17-th Annual European Symposium on Algorithms (ESA 2009), pp. 647-658.
- 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.
- 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.
- I. Razgon and B. O'Sullivan, "Almost-2-SAT is Fixed-Parameter Tractable", The 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS 5125, pp. 551-562.
- J. Chen, Y. Liu, S. Lu, B. O'Sullivan, and I. Razgon "A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem", The 40th Annual ACM Symposium on Theory of Computing (STOC 2008), pp. 177-186.
- 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.
- 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.
- 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.
- I. Razgon "Computing Minimum Directed Feedback Vertex Set in
*O*(1.9977*", The 10th Italian Conference on Theoretical Computer Science (ICTCS 2007), World Scientific, volume 6581, pp. 70-81.^{n}) - 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.
- 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.
- 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), KCL Texts in Algorithmics, volume 7, pp. 131-142. - I. Razgon "Exact Computation of Maximum Induced Forest", The 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), LNCS 4059, pp. 160-171.
- I. Razgon and A. Meisels "A CSP Search Algorithm with Reduced Branching Factor", Volume "Recent Advances in Constraints", LNAI 3978, pp. 59-72, 2006.
- I. Razgon "Complexity Analysis of Heuristic CSP Search Algorithms", Volume "Recent Advances in Constraints", LNAI 3978, pp. 88-99, 2006.
- I. Razgon and A. Meisels "CSP Search with Responsibility Sets and Kernels", The International Joint Conference on Artificial Intelligence (IJCAI 2005), pp.1533-1534.
- I. Razgon and A. Meisels "Pruning by Equally Constrained Variables", LNAI 3419, pp.26-40, 2005.
- I. Razgon and A. Meisels "Maintaining Dominance Consistency", The 9th International Conference on Principles and Practice of Constraint Programming (CP 2003), pp. 945-950.
- I. Razgon and R. Brafman "A Forward Search Planning Algorithm with a Goal Ordering Heuristic", Proceedings of the 6th European Conference on Planning (ECP 2001), pp.25-36.