A biclique is a maximal set of vertices in a graph that induces a complete bipartite subgraph. The biclique graph of a graph G is the intersection graph of all bicliques of G and we denote such graph by KB( G ). In this work we introduce the concept of biclique parts of G and the inclusion graph of biclique parts of G, denoted by BP( G ). We show that the class of BP( K 3 –free) graphs is the same as a subclass of comparability graphs which we introduce as skew-IIC comparability graphs, from which we derive a characterization of KB( K 3 –free) graphs. We also present a proper subclass of K 3 –free graphs such that its class of biclique graphs is the same as the class of biclique graphs of all K 3 –free graphs. Furthermore, it is proved that the problem of computing a preimage of a KB m ( K 3 –free) graph can be reduced to a variation of the graph sandwich problem.

A biclique is a maximal set of vertices in a graph that induces a complete bipartite graph. The biclique graph KB(G) of a graph G is the intersection graph of all bicliques in G. In this work, we introduce the concept of differentiating edges and non-edges between pairs of intersecting bicliques in a graph and the corresponding variants of the biclique graph: the edge differentiated (KBedif) and the non-edge differentiated (KBndif) biclique graphs. Two bicliques are mutually included if they can be partitioned respectively into (X1, Y1) and (X2, Y2) such that X1 c X2 and Y2 c Y1. We show that all pairs of mutually included bicliques are non-edge differentiated, but they are not edge differentiated. We show that every pair of intersecting bicliques are differentiated by either edge or non-edge. Finally, we prove that graphs are free of edge differentiated bicliques if and only if they are (K3, C5)-free and that graphs are free of non-edge differentiated bicliques if and only if they are (P4, paw)-free.

A directed hypergraph H = (V, A) is a finite set of vertices V and a set of hyper-arcs A, where each hyper-arc is an ordered pair of nonempty subsets of vertices. A flow hypergraph H = (V, A, s) is a triple, such that (V, A) is a directed hypergraph, s e V is a distinguished vertex such that s reaches every vertex of V. Reducible flow hypergraphs are a generalization of Hecht and Ullman’s reducible flowgraphs. The feedback vertex set (fvs) decision problem has a directed hypergraph H and an integer k ≥ 0 as input and the question is whether there is V'⊆V, |V' |≤k such that H\V' is an acyclic directed hypergraph. It is known that fvs is polynomial time solvable for reducible flowgraphs. In this article we prove that fvs is NP-complete for reducible flow hypergraphs showing a reduction from 3-satisfiability problem with at most 3 occurrences per variable (3sat3-). We exhibit a polynomial-time ∆-approximation for fvs in reducible flow hypergraphs, where ∆ is the maximum number of hyper-arcs adjacent to a vertex of H.

A biclique of a graph is a maximal complete bipartite subgraph. The biclique graph of a graph G, KB(G), defined as the intersection graph of the bicliques of G, was introduced and characterized in 2010 by Groshaus and Szwarcfiter. However, this characterization does not lead to polynomial time recognition algorithms, and the time complexity of its recognition problem remains open. There are some works on this problem when restricted to some classes. In this work we give a characterization of the biclique graph of a K3-free graph G. We prove that KB(G) is the square graph of a particular graph which we call Mutually Included Biclique Graph of G, KBm(G). Although it does not lead to a polynomial time recognition algorithm, it gives a new tool to prove properties of biclique graphs (restricted to K3-free graphs) using known properties of square graphs. For instance we generalize a property about induced P3's in biclique graphs to a property about stars and proved a conjecture posted by Groshaus and Montero, when restricted to K3-free graphs. Also we give another characterization of the class of biclique graphs of bipartite graphs. We prove that KB(bipartite) = (IIC-comparability)2, where IIC-comparability is a subclass of comparability graphs that we call Interval Intersection Closed Comparability.

This work presents a proposal for a cooperation system aimed to optimize flights of unmanned aerial vehicle like a quadricopter, applied to precision agriculture. The system uses technologies that allow the opening, which is the property of inserting and removing system elements at any time, and dynamicity, allowing the system to recover itself from adverse events or failures. It is also proposed a distributed optimization algorithm, that optimizes the number of points visited by the quadricopter, considering the limitation of it's autonomy. This work starts by presenting the techniques used to define the research problem, such as Problem Solving, Stakeholder Diagram, Evaluation Frame, Value Pie and Building Blocks of Culture. Next, it presents the Systematic Mapping and Systematic Review. These studies allowed to define the research problem, and propose a system to solve it, as to define the technologies used, such as Multiagent Systems, cognitive agents considering mental states, as beliefs, desires, and intentions, the negotiation among agents using FIPA Contract-Net protocol, and optimization using the proposed recursive auction algorithm. Finally, tests were developed to evaluate the proposed Multiagent System and the algorithm used to perform the recursive auctions. The Multiagent System guaranteed the opening of the system in tests with inclusion and exclusion of elements, the cognitive agents considering mental states allows the dynamicity of the system. The optimization using recursive auctions was tested in scenarios with 4, 9 and 16 points, and in all of these the optimal result was found. To minimize the processing time, as the number of message exchanges among the agents, two heuristics were proposed. After applying the heuristics, a reduction of up to 99% was achieved in the number of messages exchanged between agents in complex scenarios, like the one with 16 points.

Several social, biological and information systems can be described through complex network models. All complex networks display common structural features, such as the small-world and scale-free properties. However, the presence of selfish and/or malicious nodes can damage the network operation, as they may attack the network in several different ways, like not cooperating, or inserting, modifying or eliminating information in the network. Trust evaluation algorithms are a useful incentive for encouraging selfish nodes to collaborate or even to isolate malicious ones. Nodes that refrain from cooperation or present a malicious behavior get lower trust value and may be penalized as other nodes tend to cooperate only with highly trusted ones. This paper presents an algorithm to calculate the number of malicious and/or selfish nodes in a network based on the local trust views that each node has about their neighbors. The algorithm points out to the network manager exactly which nodes they are. Simulation results over four real complex networks demonstrate the effectiveness of the proposed approach. In fact, it presents an error margin smaller than 15% for 35 000 malicious or selfish nodes in a network of 70 000 nodes. If the number of malicious nodes goes under 5000, the error margin is around one node.

In Brazil, most Deaf children (approximately 90%) are born into non-Deaf families. These children suffer prejudice in social situations and within their own families. They have few chances to get exposed to Sign Language (SL), the natural language of the Deaf, thus being deprived of adequate language acquisition and age-appropriate intellectual development. Libras, the Brazilian Sign Language is a complete linguistic system to be used by the Deaf as a tool for communication, development, social inclusion, citizenship exercise among others. This paper presents a Human-Computer Interaction (HCI) conceptual meta-environment framework to construct computational Intellectual Artifacts in SL to promote bilingualism (Libras/Portuguese) via Intellectual Interactions (computer-mediated systems based on cognitive theories for mind development). A storytelling environment illustrates its use in order to increase family bonding activities and effective bilingualism for Deaf children and non-Deaf parents.