Location: EU Supported » PASCAL - Pattern Analysis, Statistical Modelling and Computational Learning » MLG - 2008: 6th International Workshop on Mining and Learning with Graphs

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: 53
You might be experiencing some problems with Your Video player.

Slides

Slides
0:00 Min, Max and PTIME Anti-Monotonic Overlap Graph Measures
0:20 Introduction - 1
0:45 Introduction - 2
0:59 Anti-Monotonicity - 1
1:18 Anti-Monotonicity - 2
1:55 Anti-Monotonicity - 3
2:03 Overlap Graphs - 1
2:35 Overlap Graphs - 2
3:12 Relation between Overlap Graphs
4:08 Clique Contraction
4:52 Vertex Addition
5:25 Edge Removal
5:58 Anti-Monotonic Overlap Graph Measures - 1
6:35 Anti-Monotonic Overlap Graph Measures - 2
7:01 Anti-Monotonic Overlap Graph Measures - 3
7:43 Anti-Monotonic Overlap Graph Measures - 4
7:59 Anti-Monotonic Overlap Graph Measures - 5
8:15 Anti-Monotonic Overlap Graph Measures - 6
9:08 Bounding Theorem for Meaningful Measures - 1
9:34 Bounding Theorem for Meaningful Measures - 2
9:48 Bounding Theorem for Meaningful Measures - 3
10:01 Bounding Theorem for Meaningful Measures - 4
10:10 Bounding Theorem for Meaningful Measures - 5
10:30 Bounding Theorem for Meaningful Measures - 6
10:43 Bounding Theorem for Meaningful Measures - 7
10:48 Bounding Theorem for Meaningful Measures - 8
11:03 Bounding Theorem for Meaningful Measures - 9
11:15 PTIME Computable Graph Measure - 1
11:45 PTIME Computable Graph Measure - 2
11:59 Generalization of Results of Vanetik, Gudes and Shimony - 1
12:28 Generalization of Results of Vanetik, Gudes and Shimony - 2
12:44 Generalization of Results of Vanetik, Gudes and Shimony - 3
12:48 Other Types of Matches
14:52 Extension to other Settings
16:15 Anti-Monotonic Overlap Graph Measures - 6

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.

Description

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)

Launch Windows Media PlayerLaunch in a standalone WM Player

WMedia PlayerSwitch to Windows Media Player

View slides View slides

Help icon Streaming Video Help

WebLink icon Windows Media Player Firefox Plugin - Download

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: