9 citations · 72 across the 25 of their papers we have counts for
32 papers
Restructuring Tree Decision Diagrams
Christoph Berkholz, Matthäus Micun, Igor Razgon
Tree Decision Diagrams (TDDs) are a data structure recently introduced by Capelli et al. (SAT 2026). They are structured along a vtree and the size of their canonical form lies bet…
New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth
Benjamin Bergougnoux, Tuukka Korhonen, Igor Razgon
We study the tractability of the maximum independent set problem from the viewpoint of graph width parameters, with the goal of defining a width parameter that is as general as pos…
Constant ratio FPT approximation of hypertree width parameters for hypergraphs of bounded rank
Igor Razgon
We propose an algorithm whose input are parameters and and a hypergraph of rank at most . The algorithm either returns a tree decomposition of of generalized hyp…
The treewidth and pathwidth of graph unions
Bogdan Alecu, Vadim Lozin, Daniel A. Quiroz +3
Given two -vertex graphs and of bounded treewidth, is there an -vertex graph of bounded treewidth having subgraphs isomorphic to and ? Our main res…
The splitting power of branching programs of bounded repetition and CNFs of bounded width
Igor Razgon
In this paper we study syntactic branching programs of bounded repetition representing CNFs of bounded treewidth. For this purpose we introduce two new structural graph parameters…
Classification of OBDD size for monotone 2-CNFs
Igor Razgon
We introduce a new graph parameter called linear upper maximum induced matching width \textsc{lu-mim width}, denoted for a graph by . We prove that the smallest size of…