A linear algorithm for the domination number of a series-parallel graph

DOI10.1016/0166-218X(83)90003-3zbMath0507.05060WikidataQ127220198 ScholiaQ127220198MaRDI QIDQ1837213

Noriyoshi Yoshida, Tohru Kikuno, Yoshiaki Kakuda

Publication date: 1983

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

domination numberseries-parallel decomposition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (31)

Perfect edge domination and efficient edge domination in graphs ⋮ A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs ⋮ A compact labelling scheme for series-parallel graphs ⋮ A recurrence template for several parameters in series-parallel graphs ⋮ Minimum Linear Arrangement of Series-Parallel Graphs ⋮ Minimum-maximal matching in series-parallel graphs ⋮ Some advances on the set covering polyhedron of circulant matrices ⋮ One-node cutsets and the dominating set polytope ⋮ Conflict-Free Coloring of Graphs ⋮ MAXIMUM INDEPENDENT, MINIMALLY REDUNDANT SETS IN SERIES-PARALLEL GRAPHS ⋮ Perfect Italian domination in graphs: complexity and algorithms ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ Labeling algorithms for domination problems in sun-free chordal graphs ⋮ Total domination in block graphs ⋮ Minimum <scp>color‐degree</scp> perfect b‐matchings ⋮ The price of anarchy in series-parallel network congestion games ⋮ A Dynamic Programming Approach to the Dominating Set Problem on k-Trees ⋮ On the dominating set polytope ⋮ Permutation graphs: Connected domination and Steiner trees ⋮ On minimum dominating sets with minimum intersection ⋮ Deciding whether graph \(G\) has page number one is in NC ⋮ Parallel recognition of series-parallel graphs ⋮ Total domination in interval graphs ⋮ Unnamed Item ⋮ On \(f\)-domination: polyhedral and algorithmic results ⋮ Counting dominating sets in generalized series-parallel graphs ⋮ Unnamed Item ⋮ A Survey of the Game “Lights Out!” ⋮ Perfect Roman domination in graphs ⋮ Dominating sets and domatic number of circular arc graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear algorithm for the domination number of a tree
• Some simplified NP-complete graph problems
• Optimum domination in weighted trees
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• Dividing a Graph into Triconnected Components

This page was built for publication: A linear algorithm for the domination number of a series-parallel graph