Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Maximum_disjoint_set> ?p ?o. }
Showing items 1 to 15 of
15
with 100 items per page.
- Maximum_disjoint_set abstract "In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.Finding an MDS is important in applications such as automatic label placement, VLSI circuit design, and cellular frequency division multiplexing.Every set of non-overlapping shapes is an independent set in the intersection graph of the shapes. Therefore, the MDS problem is a special case of the maximum independent set (MIS) problem. Both problems are NP complete, but finding a MDS may be easier than finding a MIS in two respects: For the general MIS problem, the best known exact algorithms are exponential. In some geometric intersection graphs, there are sub-exponential algorithms for finding a MDS. The general MIS problem is hard to approximate and doesn't even have a constant-factor approximation. In some geometric intersection graphs, there are polynomial-time approximation schemes for finding a MDS.The MDS problem can be generalized by assigning a different weight to each shape and searching for a disjoint set with a maximum total weight.In the following text, MDS(C) denotes the maximum disjoint set in a set C.".
- Maximum_disjoint_set thumbnail IntervalSelection.svg?width=300.
- Maximum_disjoint_set wikiPageExternalLink w_indep_talk.pdf.
- Maximum_disjoint_set wikiPageExternalLink rectangles.
- Maximum_disjoint_set wikiPageID "41701177".
- Maximum_disjoint_set wikiPageRevisionID "604263618".
- Maximum_disjoint_set subject Category:Computational_geometry.
- Maximum_disjoint_set comment "In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.Finding an MDS is important in applications such as automatic label placement, VLSI circuit design, and cellular frequency division multiplexing.Every set of non-overlapping shapes is an independent set in the intersection graph of the shapes. Therefore, the MDS problem is a special case of the maximum independent set (MIS) problem.".
- Maximum_disjoint_set label "Maximum disjoint set".
- Maximum_disjoint_set sameAs m.0_flsz9.
- Maximum_disjoint_set sameAs Q17163363.
- Maximum_disjoint_set sameAs Q17163363.
- Maximum_disjoint_set wasDerivedFrom Maximum_disjoint_set?oldid=604263618.
- Maximum_disjoint_set depiction IntervalSelection.svg.
- Maximum_disjoint_set isPrimaryTopicOf Maximum_disjoint_set.
