5 papers
Cluster deletion and clique partitioning in graphs with bounded clique number
Nicola Galesi, Tony Huynh, Fariba Ranjbar
The Cluster Deletion problem asks for a minimum-size edge set whose deletion turns a graph into a disjoint union of complete graphs. Equivalently, the Clique Partition problem asks…
Counting and localizing defective nodes by Boolean network tomography
Nicola Galesi, Fariba Ranjbar
Identifying defective items in larger sets is a main problem with many applications in real life situations. We consider the problem of localizing defective nodes in networks throu…
Vertex-Connectivity Measures for Node Failure Identification in Boolean Network Tomography
Nicola Galesi, Fariba Ranjbar, Michele Zito
In this paper we study the node failure identification problem in undirected graphs by means of Boolean Network Tomography. We argue that vertex connectivity plays a central role.…
Resolution and the binary encoding of combinatorial principles
Stefan Dantchev, Nicola Galesi, Barnaby Martin
We investigate the size complexity of proofs in -- an extension of Resolution working on -DNFs instead of clauses -- for families of contradictions given in the {\em un…
Space proof complexity for random 3-CNFs
Patrick Bennett, Ilario Bonacina, Nicola Galesi +3
We investigate the space complexity of refuting -CNFs in Resolution and algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a random -CNF…