Home > Search Results: keywords:"splňování omezujících podmínek|nemodulární grafy|grafové metriky|výpočetní složitost"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.01 seconds. 
Minimum 0-Extensions of Graph Metrics
 Dvořák, Martin ; Bulín, Jakub (advisor) ; Majerech, Vladan (referee)
We consider the Minimum 0-Extension Problem for a given fixed undirected graph with positive weights. We study the computational com- plexity of the threshold decision variant with respect to properties of the fixed graph, in particular modularity and orientability, as defined by Karzanov in [Eur. J. Comb., 19/1 (1998)]. We approach the problem from the viewpoint of the Finite-Valued CSP, which allows us to employ the rich theory that was developed to prove the Dichotomy Conjecture. On the negative side, we provide an explicit reduction from the Max-Cut Problem to obtain NP-hardness for non-modular graphs. For non-orientable graphs, we express a cost function that satisfies a certain condition which guarantees the existence of an implicit reduction from the Max-Cut Problem. On the positive side, we construct symmetric fractional polymorphisms in order to show that the so-called Basic LP Relaxation can solve two special cases of weighted modular orientable graphs: paths and rectangles. 1
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English