Displaying similar documents to “Algorithms for weighted graph problems on the modified cellular graph automaton”

Inferring graph grammars by detecting overlap in frequent subgraphs

Jacek P. Kukluk, Lawrence B. Holder, Diane J. Cook (2008)

International Journal of Applied Mathematics and Computer Science

Similarity:

In this paper we study the inference of node and edge replacement graph grammars. We search for frequent subgraphs and then check for an overlap among the instances of the subgraphs in the input graph. If the subgraphs overlap by one node, we propose a node replacement graph grammar production. If the subgraphs overlap by two nodes or two nodes and an edge, we propose an edge replacement graph grammar production. We can also infer a hierarchy of productions by compressing portions of...

Perfectly matchable subgraph problem on a bipartite graph

Firdovsi Sharifov (2010)

RAIRO - Operations Research

Similarity:

We consider the maximum weight perfectly matchable subgraph problem on a bipartite graph with respect to given nonnegative weights of its edges. We show that has a perfect matching if and only if some vector indexed by the nodes in is a base of an extended polymatroid associated with a submodular function defined on the subsets of . The dual problem of the separation problem for the extended polymatroid is transformed to the special maximum flow problem on . In this paper, we give...