Search results for "MathematicsofComputing_DISCRETEMATHEMATICS"
showing 10 items of 123 documents
Protein-protein interaction network querying by a "focus and zoom" approach
2008
We propose an approach to network querying in protein-protein interaction networks based on bipartite graph weighted matching. An algorithm is presented that first “focuses” the potentially relevant portion of the target graph by performing a global alignment of this one with the query graph, and then “zooms” on the actual matching nodes by considering their topological arrangement, hereby obtaining a (possibly) approximated occurrence of the query graph within the target graph. Approximation is related to node insertions, node deletions and edge deletions possibly intervening in the query graph. The technique manages networks of arbitrary topology. Moreover, edge labels are used to represe…
A branch-and-price framework for decomposing graphs into relaxed cliques
2021
We study the family of problems of partitioning and covering a graph into/with a minimum number of relaxed cliques. Relaxed cliques are subsets of vertices of a graph for which a clique-defining property—for example, the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices—is relaxed. These graph partitioning and covering problems have important applications in many areas such as social network analysis, biology, and disease-spread prevention. We propose a unified framework based on branch-and-price techniques to compute optimal decompositions. For this purpose, new, effective pricing algorithms are developed, and new…
Neighbor-Distinguishing k-tuple Edge-Colorings of Graphs
2009
AbstractThis paper studies proper k-tuple edge-colorings of graphs that distinguish neighboring vertices by their sets of colors. Minimum numbers of colors for such colorings are determined for cycles, complete graphs and complete bipartite graphs. A variation in which the color sets assigned to edges have to form cyclic intervals is also studied and similar results are given.
On the chromatic number of disk graphs
1998
Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their different generalizations. For all these graphs including the most general class of the double disk (DD) graphs, it is shown that X(G) ≤ c.ω(G) for a constant c. Several coloring algorithms are analyzed for disk graphs, aiming to improve the bounds on X(G). We find that their worst-case performance expressed in the number of used colors is indeed reached in some instances.
Calcification is not the Achilles' heel of cold-water corals in an acidifying ocean
2015
Ocean acidification is thought to be a major threat to coral reefs: laboratory evidence and CO2 seep research has shown adverse effects on many coral species, although a few are resilient. There are concerns that cold-water corals are even more vulnerable as they live in areas where aragonite saturation (?ara) is lower than in the tropics and is falling rapidly due to CO2 emissions. Here, we provide laboratory evidence that net (gross calcification minus dissolution) and gross calcification rates of three common cold-water corals, Caryophyllia smithii, Dendrophyllia cornigera, and Desmophyllum dianthus, are not affected by pCO2 levels expected for 2100 (pCO2 1058 ?atm, ?ara 1.29), and nor a…
A Combinatorial Color Edge Detector
2004
In this paper, we present an edge detection approach in color image using neighborhood hypergraph. The edge structure is detected by a structural model. The Color Image Neighborhood Hypergraph (CINH) representation is first computed, then the hyperedges of CINH are classified into noise or edge based on hypergraph properties. To evaluate the algorithm performance, experiments were carried out on synthetic and real color images corrupted by alpha-stable noise. The results show that the proposed edge detector finds the edges properly from color images.
Pattern Matching and Pattern Discovery Algorithms for Protein Topologies
2001
We describe algorithms for pattern-matching and pattern-learning in TOPS diagrams (formal descriptions of protein topologies). These problems can be reduced to checking for subgraph isomorphism and finding maximal common subgraphs in a restricted class of ordered graphs. We have developed a subgraph isomorphism algorithm for ordered graphs, which performs well on the given set of data. The maximal common subgraph problem then is solved by repeated subgraph extension and checking for isomorphisms. Despite its apparent inefficiency, this approach yields an algorithm with time complexity proportional to the number of graphs in the input set and is still practical on the given set of data. As a…
Optical Routing of Uniform Instances in Cayley Graphs
2001
Abstract Abstract We consider the problem of routing uniform communication instances in Cayley graphs. Such instances consist of all pairs of nodes whose distance is included in a specified set U. We give bounds on the load induced by these instances on the links and for the wavelength assignment problem as well. For some classes of Cayley graphs that have special symmetry property (rotational graphs), we are able to construct routings for uniform instances such that the load is the same for each link of the graph.
Orientation matters
2008
The optimal communication spanning tree (OCST) problem is a well known $\mathcal{NP}$-hard combinatorial optimization problem which seeks a spanning tree that satisfies all given communication requirements for minimal total costs. It has been shown that optimal solutions of OCST problems are biased towards the much simpler minimum spanning tree (MST) problem. Therefore, problem-specific representations for EAs like heuristic variants of edge-sets that are biased towards MSTs show high performance.In this paper, additional properties of optimal solutions for Euclidean variants of OCST problems are studied. Experimental results show that not only edges in optimal trees are biased towards low-…
An algorithm for the Rural Postman problem on a directed graph
1986
The Directed Rural Postman Problem (DRPP) is a general case of the Chinese Postman Problem where a subset of the set of arcs of a given directed graph is ‘required’ to be traversed at minimum cost. If this subset does not form a weakly connected graph but forms a number of disconnected components the problem is NP-Complete, and is also a generalization of the asymmetric Travelling Salesman Problem. In this paper we present a branch and bound algorithm for the exact solution of the DRPP based on bounds computed from Lagrangean Relaxation (with shortest spanning arborescence sub-problems) and on the fathoming of some of the tree nodes by the solution of minimum cost flow problems. Computation…