9 citations · 72 across the 25 of their papers we have counts for
7 papers · 1 filter
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…
Tree-width dichotomy
Vadim Lozin, Igor Razgon
We prove that the tree-width of graphs in a hereditary class defined by a finite set of forbidden induced subgraphs is bounded if and only if includes a complete graph, a c…
Linear read-once and related Boolean functions
Vadim Lozin, Igor Razgon, Viktor Zamaraev +2
It is known that a positive Boolean function f depending on n variables has at least n + 1 extremal points, i.e. minimal ones and maximal zeros. We show that f has exactly n + 1 ex…
Specifying a positive threshold function via extremal points
Vadim Lozin, Igor Razgon, Viktor Zamaraev +2
An extremal point of a positive threshold Boolean function is either a maximal zero or a minimal one. It is known that if depends on all its variables, then the set of its…