3 citations · 3 across the 8 of their papers we have counts for
8 papers
Maximum independent set (stable set) problem: Computational testing with binary search and convex programming using a bin packing approach
Prabhu Manyem
This paper deals with the maximum independent set (M.I.S.) problem, also known as the stable set problem. The basic mathematical programming model that captures this problem is an…
Decision versions of optimization problems: cardinality constraint (lower bound) as a CNF Horn formula for Maximum Matching
Prabhu Manyem
We provide a formula for the lower bound in the form of , in such a way that the decision version of unweighted non-bipartite matching can be solved in polynomial time.…
Expressibility at the machine level versus structure level: ESO universal Horn Logic and the class P
Prabhu Manyem
We show that ESO universal Horn logic (existential second logic where the first order part is a universal Horn formula) is insufficient to capture P, the class of problems decidabl…
Duality Gap, Computational Complexity and NP Completeness: A Survey
Prabhu Manyem
We survey research that studies the connection between the computational complexity of optimization problems on the one hand, and the duality gap between the primal and dual optimi…
Existential Second Order Logic Expression With Horn First Order for Maximum Clique (Decision Version)
Prabhu Manyem
We show that the maximum clique problem (decision version) can be expressed in existential second order (ESO) logic, where the first order part is a Horn formula in second-order qu…
Clique and Vertex Cover are solvable in polynomial time if the input structure is ordered and contains a successor predicate
Prabhu Manyem
In this manuscript, assuming that Graedel's 1991 results are correct (which implies that bounds on the solution values for optimization problems can be expressed in existential sec…
Lower Bounds on Syntactic Logic Expressions for Optimization Problems and Duality using Lagrangian Dual to characterize optimality conditions
Prabhu Manyem
We show that simple syntactic expressions such as existential second order (ESO) universal Horn formulae can express NP-hard optimisation problems. There is a significant differenc…
Syntactic Characterisations of Polynomial-Time Optimisation Classes (Syntactic Characterizations of Polynomial-Time Optimization Classes)
Prabhu Manyem
In Descriptive Complexity, there is a vast amount of literature on decision problems, and their classes such as \textbf{P, NP, L and NL}. ~ However, research on the descriptive com…