ScholarLens Back to search
1980•SIAM Journal on Applied MathematicsRequires access

Edge Dominating Sets in Graphs

Mihalis Yannakakis, Fǎnicǎ Gavril

Open publisher page 395 citations

Abstract

We prove that the edge dominating set problem for graphs is $NP$-complete even when restricted to planar or bipartite graphs of maximum degree 3. We show as a corollary that the minimum maximal matching and the achromatic number problems are $NP$-complete. A new linear time algorithm for finding minimum independent edge dominating sets in trees is described, based on an observed relationship between edge dominating sets and independent sets in total graphs.

About this research paper

What this paper is about

We prove that the edge dominating set problem for graphs is $NP$-complete even when restricted to planar or bipartite graphs of maximum degree 3. We show as a corollary that the minimum maximal matching and the achromatic number problems are $NP$-complete. A new linear time algorithm for finding minimum independent edge dominating sets in trees is described, based on an observed relationship between edge dominating sets and independent sets in total graphs.

Why it matters

OpenAlex reports 395 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

We prove that the edge dominating set problem for graphs is $NP$-complete even when restricted to planar or bipartite graphs of maximum degree 3. We show as a corollary that the minimum maximal matching and the achromatic number problems are $NP$-complete. A new linear time algorithm for finding minimum independent edge dominating sets in trees is described, based on an observed relationship between edge dominating sets and independent sets in total graphs.

Key concepts: Combinatorics, Mathematics, Maximal independent set, Dominating set, Bipartite graph, Corollary, Chordal graph, Enhanced Data Rates for GSM Evolution

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
Edge Dominating Sets in Graphs — Research Paper | ScholarLens