Min, Max and PTIME Anti-Monotonic Overlap Graph Measures

author: Dries Van Dyck, Transnational University of Limburg
published: Aug. 25, 2008,   recorded: July 2008,   views: 3079


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


The main contributions of this paper are: (1) We extend the anti-monotonicity results of Vanetik, Gudes and Shimony to all 24 combinations of iso-, homo-, or homeomorphism, on labeled or unlabeled, directed or undirected graphs, with edge- or vertex-overlap. (2) We show that (under reasonable assumptions) the maximum independent set measure (MIS) of Vanetik, Gudes and Shimony (2006) is the smallest anti-monotonic measure in the class of overlap-graph based frequency measures. We also introduce the new minimum clique partition measure (MCP) which represents the largest possible one. (3) In general, both theMIS and theMCP measure are NP-hard in the size of the overlap graph. We introduce the polynomial time computable Lovasz measure, which is is sandwiched between the former two, and show that is anti-monotonic.

See Also:

Download slides icon Download slides: mlg08_van_dyck_mmp_01.pdf (390.3┬áKB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: