Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Maximum_disjoint_set> ?p ?o }
Showing triples 1 to 46 of
46
with 100 triples 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 (PTAS) 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 wikiPageLength "27911".
- Maximum_disjoint_set wikiPageOutDegree "36".
- Maximum_disjoint_set wikiPageRevisionID "679465265".
- Maximum_disjoint_set wikiPageWikiLink Automatic_label_placement.
- Maximum_disjoint_set wikiPageWikiLink Category:Computational_geometry.
- Maximum_disjoint_set wikiPageWikiLink Computational_geometry.
- Maximum_disjoint_set wikiPageWikiLink Dynamic_programming.
- Maximum_disjoint_set wikiPageWikiLink Earliest_deadline_first_scheduling.
- Maximum_disjoint_set wikiPageWikiLink Fat_object.
- Maximum_disjoint_set wikiPageWikiLink Frequency-division_multiplexing.
- Maximum_disjoint_set wikiPageWikiLink Geometric_separator.
- Maximum_disjoint_set wikiPageWikiLink Greedy_algorithm.
- Maximum_disjoint_set wikiPageWikiLink Independent_set_(graph_theory).
- Maximum_disjoint_set wikiPageWikiLink Intersection_graph.
- Maximum_disjoint_set wikiPageWikiLink Interval_scheduling.
- Maximum_disjoint_set wikiPageWikiLink Linear_programming_relaxation.
- Maximum_disjoint_set wikiPageWikiLink Local_search_(optimization).
- Maximum_disjoint_set wikiPageWikiLink NP-completeness.
- Maximum_disjoint_set wikiPageWikiLink Pigeonhole_principle.
- Maximum_disjoint_set wikiPageWikiLink Polynomial-time_approximation_scheme.
- Maximum_disjoint_set wikiPageWikiLink Quadtree.
- Maximum_disjoint_set wikiPageWikiLink Regular_polygon.
- Maximum_disjoint_set wikiPageWikiLink Union_complexity.
- Maximum_disjoint_set wikiPageWikiLink Very-large-scale_integration.
- Maximum_disjoint_set wikiPageWikiLink File:IntersectingDisks.svg.
- Maximum_disjoint_set wikiPageWikiLink File:IntersectingUnitDisks.svg.
- Maximum_disjoint_set wikiPageWikiLink File:IntervalSelection.svg.
- Maximum_disjoint_set wikiPageWikiLink File:Point_quadtree.svg.
- Maximum_disjoint_set wikiPageWikiLinkText "Maximum disjoint set".
- Maximum_disjoint_set wikiPageWikiLinkText "Maximum disjoint sets".
- Maximum_disjoint_set wikiPageUsesTemplate Template:Reflist.
- Maximum_disjoint_set subject Category:Computational_geometry.
- Maximum_disjoint_set hypernym Set.
- 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 Q17163363.
- Maximum_disjoint_set sameAs m.0_flsz9.
- Maximum_disjoint_set sameAs Q17163363.
- Maximum_disjoint_set wasDerivedFrom Maximum_disjoint_set?oldid=679465265.
- Maximum_disjoint_set depiction IntervalSelection.svg.
- Maximum_disjoint_set isPrimaryTopicOf Maximum_disjoint_set.