The efficiency of AC graphs (Q686253)
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 428108
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The efficiency of AC graphs |
scientific article; zbMATH DE number 428108 |
Statements
The efficiency of AC graphs (English)
0 references
28 November 1993
0 references
If \(G=(V,e)\) is an undirected graph with a distinguished subset \(R \subset V\), then a vertex \(v \in V \backslash R\) is said to be dominated by \(s \in R\), if \(v\) and \(s\) are connected by an edge. The maximum efficiency \(\varepsilon(G)\) is the maximum number of vertices in \(V \backslash R\) over all subsets \(R \subset V\) that are dominated by exactly one node in \(R\). Expanding a result of \textit{P. J. Bernhard}, \textit{S. T. Hedetniemi} and \textit{D. P. Jacobs} [ibid. 44, 99-108 (1993; Zbl 0780.68097)], the present author constructs a linear time algorithm for computing \(\varepsilon(G)\) when \(G\) is an \(AC\) graph.
0 references
dominated vertex
0 references
maximum efficiency
0 references
\(AC\) graphs
0 references
0.8137187957763672
0 references
0.8123825192451477
0 references
0.7956986427307129
0 references
0.7870936393737793
0 references
