Maximum Common Induced Subgraph (MCIS)

From GM-RKB
(Redirected from common induced subgraph)
Jump to navigation Jump to search

A Maximum Common Induced Subgraph (MCIS) is a Maximum Common Subgraph that is an induced graph of two graphs in which their common nodes in common their respective end‐points are preserved.



References

2018a

2018b

  1. Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 A1.4: GT48, pg.202.
  2. Kann, Viggo (1992), "On the approximability of the maximum common subgraph problem", STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science Cachan, France, February 13–15, 1992, Proceedings, Lecture Notes in Computer Science, 577, Springer Science $\mathplus$ Business Media, pp. 375–388, doi:10.1007/3-540-55210-3_198.
  3. Zuckerman, D. (2006), "Linear degree extractors and the inapproximability of max clique and chromatic number", Proc. 38th ACM Symp. Theory of Computing, pp. 681–690, doi:10.1145/1132516.1132612, ISBN 1-59593-134-1, ECCC TR05-100.
  4. Barrow, H.; Burstall, R. (1976), "Subgraph isomorphism, matching relational structures and maximal cliques", Information Processing Letters, 4 (4): 83–84, doi:10.1016/0020-0190(76)90049-1.
  5. Raymond, John W.; Willett, Peter (2002)

2018c

2002