Exact arborescences, matchings and cycles (Q1095157)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4027518
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Exact arborescences, matchings and cycles |
scientific article; zbMATH DE number 4027518 |
Statements
Exact arborescences, matchings and cycles (English)
0 references
1987
0 references
Given a graph in which each edge has an integral weight, an exact problem is to determine whether a desired structure exists for which the sum of the edge weights is exactly k for some specified k. Given a directed graph with a specified vertex r, an arborescence rooted at r is a set of arcs which induce a connected directed subgraph such that r has indegree zero and all other vertices have indegree one. The existence of polynomial algorithms is shown for exact arborescence, exact spanning tree, exact perfect matching in planar graphs, and exact cycle sum for a class of planar directed graphs.
0 references
directed graph
0 references
arborescence
0 references
polynomial algorithms
0 references
exact spanning tree
0 references
exact perfect matching
0 references
planar graphs
0 references
exact cycle
0 references
planar directed graphs
0 references
0.7833571434020996
0 references
0.7809515595436096
0 references
0.7704148292541504
0 references
0.7700223922729492
0 references
