Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Constraint_Composite_Graph> ?p ?o }
Showing triples 1 to 40 of
40
with 100 triples per page.
- Constraint_Composite_Graph abstract "The constraint composite graph is a node-weighted undirected graph associated with a given combinatorial optimization problem posed as a weighted constraint satisfaction problem. Developed and introduced by Satish Kumar Thittamaranahalli (T. K. Satish Kumar), the idea of the constraint composite graph is a big step towards unifying different approaches for exploiting "structure" in weighted constraint satisfaction problems.A weighted constraint satisfaction problem is a generalization of a constraint satisfaction problem in which the constraints are no longer "hard," but are extended to specify non-negative costs associated with the tuples. The goal is then to find an assignment of values to all the variables from their respective domains so that the total cost is minimized. Weighted constraint satisfaction problems find innumerable applications in artificial intelligence and computer science. They are also variously referred to as markov random fields (in statistics and signal processing) and energy minimization problems (in physics).While weighted constraint satisfaction problems are NP-hard to solve in general, several subclasses can be solved in polynomial time when their weighted constraints exhibit specific kinds of numerical structure. Tractable subclasses can also be identified by analyzing the way constraints are placed over the variables. Specifically, a weighted constraint satisfaction problem can be solved in time exponential only in the treewidth of its variable-interaction graph (constraint network). However, a major drawback of the constraint network is that it does not provide a computational framework for leveraging the numerical structure of the weighted constraints.Unlike the constraint network, the constraint composite graph provides a unifying framework for representing both the graphical structure of the variable-interactions as well as the numerical structure of the weighted constraints. It can be constructed using a simple polynomial-time procedure; and a given weighted constraint satisfaction problem is reducible to the problem of computing the minimum weighted vertex cover for its associated constraint composite graph. The "hybrid" computational properties of the constraint composite graph are reflected in the following two important results:(Result 1) The constraint composite graph of a given weighted constraint satisfaction problem has the same treewidth as its associated constraint network.(Result 2) Many subclasses of weighted constraint satisfaction problems that are tractable by virtue of the numerical structure of their weighted constraints have associated constraint composite graphs that are bipartite in nature.Result 1 shows that the constraint composite graph can be used to capture the graphical structure of the variable-interactions (since a minimum weighted vertex cover for any graph can be computed in time exponential only in the treewidth of that graph). Result 2 shows that the constraint composite graph can also be used to capture the numerical structure of the weighted constraints (since a minimum weighted vertex cover can be computed in polynomial time for bipartite graphs).".
- Constraint_Composite_Graph wikiPageID "21979895".
- Constraint_Composite_Graph wikiPageLength "3835".
- Constraint_Composite_Graph wikiPageOutDegree "18".
- Constraint_Composite_Graph wikiPageRevisionID "541597788".
- Constraint_Composite_Graph wikiPageWikiLink Artificial_intelligence.
- Constraint_Composite_Graph wikiPageWikiLink Bipartite_graph.
- Constraint_Composite_Graph wikiPageWikiLink Category:Constraint_programming.
- Constraint_Composite_Graph wikiPageWikiLink Combinatorial_optimization.
- Constraint_Composite_Graph wikiPageWikiLink Computer_science.
- Constraint_Composite_Graph wikiPageWikiLink Constraint_satisfaction_problem.
- Constraint_Composite_Graph wikiPageWikiLink Energy_minimization.
- Constraint_Composite_Graph wikiPageWikiLink Generalization.
- Constraint_Composite_Graph wikiPageWikiLink Markov_random_field.
- Constraint_Composite_Graph wikiPageWikiLink NP-hard.
- Constraint_Composite_Graph wikiPageWikiLink NP-hardness.
- Constraint_Composite_Graph wikiPageWikiLink Non-negative.
- Constraint_Composite_Graph wikiPageWikiLink Physics.
- Constraint_Composite_Graph wikiPageWikiLink Polynomial_time.
- Constraint_Composite_Graph wikiPageWikiLink Sign_(mathematics).
- Constraint_Composite_Graph wikiPageWikiLink Signal_processing.
- Constraint_Composite_Graph wikiPageWikiLink Statistics.
- Constraint_Composite_Graph wikiPageWikiLink Time_complexity.
- Constraint_Composite_Graph wikiPageWikiLink Treewidth.
- Constraint_Composite_Graph wikiPageWikiLink Tuple.
- Constraint_Composite_Graph wikiPageWikiLink Vertex_cover.
- Constraint_Composite_Graph hasPhotoCollection Constraint_Composite_Graph.
- Constraint_Composite_Graph wikiPageUsesTemplate Template:Orphan.
- Constraint_Composite_Graph subject Category:Constraint_programming.
- Constraint_Composite_Graph hypernym Graph.
- Constraint_Composite_Graph type Article.
- Constraint_Composite_Graph type Software.
- Constraint_Composite_Graph type Article.
- Constraint_Composite_Graph comment "The constraint composite graph is a node-weighted undirected graph associated with a given combinatorial optimization problem posed as a weighted constraint satisfaction problem. Developed and introduced by Satish Kumar Thittamaranahalli (T. K.".
- Constraint_Composite_Graph label "Constraint Composite Graph".
- Constraint_Composite_Graph sameAs m.05p8cdl.
- Constraint_Composite_Graph sameAs Q5164364.
- Constraint_Composite_Graph sameAs Q5164364.
- Constraint_Composite_Graph wasDerivedFrom Constraint_Composite_Graph?oldid=541597788.
- Constraint_Composite_Graph isPrimaryTopicOf Constraint_Composite_Graph.