Matches in DBpedia 2014 for { <http://dbpedia.org/resource/MaxDDBS> ?p ?o. }
Showing items 1 to 21 of
21
with 100 items per page.
- MaxDDBS abstract "The Maximum Degree-and-Diameter-Bounded Subgraph problem (MaxDDBS) is a problem in graph theory. Given a connected host graph G, an upper bound for the degree d, and an upper bound for the diameter k, we look for the largest subgraph S of G with maximum degree at most d and diameter at most k. This problem is also referred to as the Degree-Diameter Subgraph Problem, as it contains the degree diameter problem as a special case (namely, by taking a sufficiently large complete graph as a host graph). Despite being a natural generalization of the Degree-Diameter Problem, MaxDDBS only began to be investigated in 2011, while research in the Degree-Diameter Problem has been active since the 1960s. Regarding its computational complexity, the problem is NP-hard, and not in APX (i.e. it cannot be approximated to within a constant factor in polynomial time).".
- MaxDDBS wikiPageExternalLink The_Maximum_Degree-and-Diameter-Bounded_Subgraph_Problem.
- MaxDDBS wikiPageID "32377002".
- MaxDDBS wikiPageRevisionID "489654634".
- MaxDDBS hasPhotoCollection MaxDDBS.
- MaxDDBS subject Category:Computational_problems_in_graph_theory.
- MaxDDBS type Abstraction100002137.
- MaxDDBS type Attribute100024264.
- MaxDDBS type ComputationalProblemsInGraphTheory.
- MaxDDBS type Condition113920835.
- MaxDDBS type Difficulty114408086.
- MaxDDBS type Problem114410605.
- MaxDDBS type State100024720.
- MaxDDBS comment "The Maximum Degree-and-Diameter-Bounded Subgraph problem (MaxDDBS) is a problem in graph theory. Given a connected host graph G, an upper bound for the degree d, and an upper bound for the diameter k, we look for the largest subgraph S of G with maximum degree at most d and diameter at most k.".
- MaxDDBS label "MaxDDBS".
- MaxDDBS sameAs m.0gyvbb1.
- MaxDDBS sameAs Q6794498.
- MaxDDBS sameAs Q6794498.
- MaxDDBS sameAs MaxDDBS.
- MaxDDBS wasDerivedFrom MaxDDBS?oldid=489654634.
- MaxDDBS isPrimaryTopicOf MaxDDBS.