An exact algorithm based on chain implication for the Min-CVCB problem
The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem), with important applications in the study of reconfigurable arrays in VLSI design, is an NP-hard problem and has attracted considerable attention in the literature. Based on a deeper and more careful analysis on the structures of bipartite graphs, we develop an exact algorithm of running time O((ku+kl)|G|+1.1892ku+kl), which improves the best previous algorithm of running time O((ku + kl)|G| + 1.26ku+kl) for the problem.
We report on a formal verification of the Alternating Bit Protocol (ABP) in the Calculus of Constructions. ::: We outline a semi-formal correctness proof of the ABP with sufficient detail to be formalised. Thereafter ::: we show by examples how the formalised proof has been verified by the automated proof checker Coq. ::: This is part of an ongoing project aiming at the mechanisation of reasoning in (extensions of) process ::: algebra, which we think important for the fruitful application of process algebra to concurrent systems.