![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Igor Razgon
Person information
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [j20]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): 261-276 (2024) - [c34]Matthias Lanzinger, Igor Razgon:
FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs. STACS 2024: 48:1-48:17 - 2023
- [j19]Georg Gottlob, Matthias Lanzinger
, Reinhard Pichler, Igor Razgon:
Fractional covers of hypergraphs with bounded multi-intersection. Theor. Comput. Sci. 979: 114204 (2023) - [c33]Benjamin Bergougnoux
, Tuukka Korhonen
, Igor Razgon:
New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth. WG 2023: 72-85 - [i34]Benjamin Bergougnoux, Tuukka Korhonen, Igor Razgon:
New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth. CoRR abs/2302.10643 (2023) - [i33]Matthias Lanzinger, Igor Razgon:
FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs. CoRR abs/2309.17049 (2023) - 2022
- [j18]Vadim V. Lozin, Igor Razgon:
Tree-width dichotomy. Eur. J. Comb. 103: 103517 (2022) - [i32]Igor Razgon:
The splitting power of branching programs of bounded repetition and CNFs of bounded width. CoRR abs/2201.02173 (2022) - [i31]Bogdan Alecu, Vadim V. Lozin, Daniel A. Quiroz, Roman Rabinovich, Igor Razgon, Viktor Zamaraev:
The treewidth and pathwidth of graph unions. CoRR abs/2202.07752 (2022) - [i30]Igor Razgon:
FPT algoritms providing constant ratio approximation of hypertree width parameters for hypergraphs of bounded rank. CoRR abs/2212.13423 (2022) - 2021
- [j17]Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon:
Complexity Analysis of Generalized and Fractional Hypertree Decompositions. J. ACM 68(5): 38:1-38:50 (2021) - [c32]Igor Razgon:
Classification of OBDD Size for Monotone 2-CNFs. IPEC 2021: 25:1-25:15 - [i29]Igor Razgon:
Classification of OBDD size for monotone 2-CNFs. CoRR abs/2103.09115 (2021) - [i28]Igor Razgon:
Classification of OBDD size for monotone 2-CNFs. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [c31]Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon:
Fractional Covers of Hypergraphs with Bounded Multi-Intersection. MFCS 2020: 41:1-41:14 - [i27]Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon:
Complexity Analysis of General and Fractional Hypertree Decompositions. CoRR abs/2002.05239 (2020) - [i26]Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, Igor Razgon:
Fractional Covers of Hypergraphs with Bounded Multi-Intersection. CoRR abs/2007.01830 (2020) - [i25]Vadim V. Lozin, Igor Razgon:
Tree-width dichotomy. CoRR abs/2012.01115 (2020)
2010 – 2019
- 2019
- [i24]Andrea Calì, Igor Razgon:
Regular resolution for CNF of bounded incidence treewidth with few long clauses. CoRR abs/1905.10867 (2019) - 2018
- [j16]Vadim V. Lozin, Igor Razgon, Viktor Zamaraev
, Elena Zamaraeva
, Nikolai Yu. Zolotykh
:
Linear read-once and related Boolean functions. Discret. Appl. Math. 250: 16-27 (2018) - [j15]Vadim V. Lozin, Igor Razgon, Viktor Zamaraev
:
Well-quasi-ordering versus clique-width. J. Comb. Theory B 130: 1-18 (2018) - [i23]Vadim V. Lozin, Igor Razgon, Viktor Zamaraev, Elena Zamaraeva, Nikolai Yu. Zolotykh:
Linear read-once and related Boolean functions. CoRR abs/1805.10159 (2018) - 2017
- [j14]Igor Razgon:
On Oblivious Branching Programs with Bounded Repetition that Cannot Efficiently Compute CNFs of Bounded Treewidth. Theory Comput. Syst. 61(3): 755-776 (2017) - [c30]Vadim V. Lozin, Igor Razgon, Viktor Zamaraev, Elena Zamaraeva, Nikolai Yu. Zolotykh:
Specifying a positive threshold function via extremal points. ALT 2017: 208-222 - [c29]Andrea Calì, Davide Martinenghi, Igor Razgon, Martín Ugarte:
Querying the Deep Web: Back to the Foundations. AMW 2017 - [i22]Vadim V. Lozin, Igor Razgon, Victor Zamaraev, Elena Zamaraeva, Nikolai Yu. Zolotykh:
Specifying a positive threshold function via extremal points. CoRR abs/1706.01747 (2017) - [i21]Andrea Calì, Florent Capelli, Igor Razgon:
Non-FPT lower bounds for structural restrictions of decision DNNF. CoRR abs/1708.07767 (2017) - [i20]Igor Razgon:
Partial matching width and its application to lower bounds for branching programs. CoRR abs/1709.08890 (2017) - 2016
- [j13]Igor Razgon:
On the Read-Once Property of Branching Programs and CNFs of Bounded Treewidth. Algorithmica 75(2): 277-294 (2016) - [i19]Oded Lachish, Igor Razgon:
Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs. CoRR abs/1604.01560 (2016) - 2015
- [c28]Igor Razgon:
Quasipolynomial Simulation of DNNF by a Non-determinstic Read-Once Branching Program. CP 2015: 367-375 - [c27]Vadim V. Lozin
, Igor Razgon, Victor Zamaraev
:
Well-quasi-ordering Does Not Imply Bounded Clique-width. WG 2015: 351-359 - [i18]Vadim V. Lozin, Igor Razgon, Victor Zamaraev:
Well-quasi-ordering does not imply bounded clique-width. CoRR abs/1503.00571 (2015) - [i17]Igor Razgon:
On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth. CoRR abs/1510.02951 (2015) - [i16]Igor Razgon:
Two types of branching programs with bounded repetition that cannot efficiently compute monotone 3-CNFs. CoRR abs/1510.05486 (2015) - 2014
- [j12]Dániel Marx, Igor Razgon:
Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset. SIAM J. Comput. 43(2): 355-388 (2014) - [c26]Igor Razgon:
No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth. IPEC 2014: 319-331 - [c25]Igor Razgon:
On OBDDs for CNFs of Bounded Treewidth. KR 2014 - [c24]Andrea Calì, Igor Razgon:
Complexity of Conjunctive Query Answering under Access Limitations (Preliminary Report). SEBD 2014: 256-263 - [i15]Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan, Igor Razgon:
Soft Constraints of Difference and Equality. CoRR abs/1401.3879 (2014) - [i14]Igor Razgon:
No small nondeterministic read-once branching programs for CNFs of bounded treewidth. CoRR abs/1407.0491 (2014) - [i13]Igor Razgon:
On the read-once property of branching programs and CNFs of bounded treewidth. CoRR abs/1411.0264 (2014) - 2013
- [j11]Nicholas Korpelainen
, Vadim V. Lozin
, Igor Razgon:
Boundary Properties of Well-Quasi-Ordered Sets of Graphs. Order 30(3): 723-735 (2013) - [j10]Dániel Marx, Barry O'Sullivan
, Igor Razgon:
Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9(4): 30:1-30:35 (2013) - [c23]Igor Razgon, Justyna Petke
:
Cliquewidth and Knowledge Compilation. SAT 2013: 335-350 - [i12]Igor Razgon, Justyna Petke:
Cliquewidth and Knowledge Compilation. CoRR abs/1303.4081 (2013) - [i11]Igor Razgon:
On OBDDs for CNFs of bounded treewidth. CoRR abs/1308.3829 (2013) - 2012
- [c22]Aistis Atminas, Vadim V. Lozin
, Igor Razgon:
Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths. SWAT 2012: 142-152 - 2011
- [j9]Emmanuel Hebrard
, Dániel Marx, Barry O'Sullivan
, Igor Razgon:
Soft Constraints of Difference and Equality. J. Artif. Intell. Res. 41: 97-130 (2011) - [c21]Dániel Marx, Igor Razgon:
Fixed-parameter tractability of multicut parameterized by the size of the cutset. STOC 2011: 469-478 - [i10]Igor Razgon:
Large Isolating Cuts Shrink the Multiway Cut. CoRR abs/1104.5361 (2011) - [i9]Dániel Marx, Barry O'Sullivan, Igor Razgon:
Finding small separators in linear time via treewidth reduction. CoRR abs/1110.4765 (2011) - 2010
- [c20]Dániel Marx, Barry O'Sullivan, Igor Razgon:
Treewidth Reduction for Constrained Separation and Bipartization Problems. STACS 2010: 561-572 - [i8]Dániel Marx, Igor Razgon:
Fixed-parameter tractability of multicut parameterized by the size of the cutset. CoRR abs/1010.3633 (2010) - [i7]Igor Razgon:
Computing multiway cut within the given excess over the largest minimum isolating cut. CoRR abs/1011.6267 (2010)
2000 – 2009
- 2009
- [j8]Dániel Marx, Igor Razgon:
Constant ratio fixed-parameter approximation of the edge multicut problem. Inf. Process. Lett. 109(20): 1161-1166 (2009) - [j7]Igor Razgon, Barry O'Sullivan
:
Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci. 75(8): 435-450 (2009) - [j6]Igor Razgon:
Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3. J. Discrete Algorithms 7(2): 191-212 (2009) - [j5]Gregory Z. Gutin, Igor Razgon, Eun Jung Kim:
Minimum leaf out-branching and related problems. Theor. Comput. Sci. 410(45): 4571-4579 (2009) - [c19]Emmanuel Hebrard
, Dániel Marx, Barry O'Sullivan
, Igor Razgon:
Constraints of Difference and Equality: A Complete Taxonomic Characterisation. CP 2009: 424-438 - [c18]Dániel Marx, Igor Razgon:
Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem. ESA 2009: 647-658 - [c17]Gregory Z. Gutin, Daniel Karapetyan
, Igor Razgon:
Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs. IWPEC 2009: 222-233 - [c16]Daniel Johannsen, Igor Razgon, Magnus Wahlström:
Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences. SAT 2009: 80-85 - [i6]Dániel Marx, Barry O'Sullivan, Igor Razgon:
Treewidth reduction for constrained separation and bipartization problems. CoRR abs/0902.3780 (2009) - [i5]Gregory Z. Gutin, Daniel Karapetyan, Igor Razgon:
FPT Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs. CoRR abs/0906.1359 (2009) - 2008
- [j4]Fedor V. Fomin
, Serge Gaspers, Artem V. Pyatkin
, Igor Razgon:
On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms. Algorithmica 52(2): 293-307 (2008) - [j3]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): 21:1-21:19 (2008) - [c15]Gregory Z. Gutin, Igor Razgon, Eun Jung Kim:
Minimum Leaf Out-Branching Problems. AAIM 2008: 235-246 - [c14]Emmanuel Hebrard
, Barry O'Sullivan
, Igor Razgon:
A Soft Constraint of Equality: Complexity and Approximability. CP 2008: 358-371 - [c13]Igor Razgon, Barry O'Sullivan
:
Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract). ICALP (1) 2008: 551-562 - [c12]Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon:
A fixed-parameter algorithm for the directed feedback vertex set problem. STOC 2008: 177-186 - [i4]Igor Razgon, Barry O'Sullivan:
Almost 2-SAT is Fixed-Parameter Tractable. CoRR abs/0801.1300 (2008) - [i3]Gregory Z. Gutin, Eun Jung Kim, Igor Razgon:
Minimum Leaf Out-Branching Problems. CoRR abs/0801.1979 (2008) - 2007
- [j2]Igor Razgon, Amnon Meisels:
A CSP Search Algorithm with Responsibility Sets and Kernels. Constraints An Int. J. 12(2): 151-177 (2007) - [j1]Igor Razgon:
A 2O(k)poly(n) algorithm for the parameterized Convex Recoloring problem. Inf. Process. Lett. 104(2): 53-58 (2007) - [c11]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: 75-85 - [c10]Igor Razgon, Barry O'Sullivan, Gregory M. Provan:
Generalizing Global Constraints Based on Network Flows. CSCLP 2007: 127-141 - [c9]Igor Razgon:
Computing Minimum Directed Feedback Vertex Set in O(1.9977n). ICTCS 2007: 70-81 - [i2]Igor Razgon, Barry O'Sullivan:
Directed Feedback Vertex Set is Fixed-Parameter Tractable. Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs 2007 - [i1]Igor Razgon, Barry O'Sullivan:
Directed Feedback Vertex Set is Fixed-Parameter Tractable. CoRR abs/0707.0282 (2007) - 2006
- [c8]Igor Razgon:
A Faster Solving of the Maximum Independent Set Problem for Graphs with Maximal Degree 3. ACiD 2006: 131-142 - [c7]Igor Razgon, Barry O'Sullivan:
Efficient Recognition of Acyclic Clustered Constraint Satisfaction Problems. CSCLP 2006: 154-168 - [c6]Igor Razgon:
Exact Computation of Maximum Induced Forest. SWAT 2006: 160-171 - 2005
- [c5]Igor Razgon, Amnon Meisels:
A CSP Search Algorithm with Reduced Branching Factor. CSCLP 2005: 59-72 - [c4]Igor Razgon:
Complexity Analysis of Heuristic CSP Search Algorithms. CSCLP 2005: 88-99 - [c3]Igor Razgon, Amnon Meisels:
CSP Search with Responsibility Sets and Kernels. IJCAI 2005: 1533-1534 - 2004
- [c2]Igor Razgon, Amnon Meisels:
Pruning by Equally Constrained Variables. CSCLP 2004: 26-40 - 2003
- [c1]Igor Razgon, Amnon Meisels:
Maintaining Dominance Consistency. CP 2003: 945-949
Coauthor Index
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-06-10 21:28 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint