Abstract | ||
---|---|---|
A cograph (complement reducible graph) is a graph which can be generated by disjoint union and complement operations on graphs, starting with a single vertex graph. Cographs arise in many areas of computer science and are studied extensively. With the goal of developing an effective data mining method for graph structured data, in this paper we introduce a graph pattern expression, called a cograph pattern, which is a special type of cograph having structured variables. Firstly, we present a polynomial time matching algorithm for cograph patterns. Secondly, we give a polynomial time algorithm for obtaining a minimally generalized cograph pattern which explains given positive data. Finally, we show that the class of cograph pattern languages is polynomial time inductively inferable from positive data. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1007/978-3-642-31951-8_32 | ILP |
Keywords | Field | DocType |
polynomial time inductive inference,effective data mining method,cograph pattern language,cograph pattern,graph pattern expression,minimally generalized cograph pattern,single vertex graph,polynomial time,polynomial time algorithm,reducible graph,positive data | Computer science,Vertex (graph theory),Theoretical computer science,Artificial intelligence,Time complexity,Disjoint union,Graph operations,Graph,Inductive reasoning,Discrete mathematics,Combinatorics,Cograph,Blossom algorithm,Machine learning | Conference |
Citations | PageRank | References |
2 | 0.37 | 10 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yuta Yoshimura | 1 | 4 | 1.12 |
Takayoshi Shoudai | 2 | 269 | 31.89 |
Yusuke Suzuki | 3 | 150 | 18.82 |
Tomoyuki Uchida | 4 | 255 | 35.06 |
Tetsuhiro Miyahara | 5 | 267 | 32.75 |