MAXIMUM INDEPENDENT, MINIMALLY REDUNDANT SETS IN SERIES-PARALLEL GRAPHS

DOI10.1080/16073606.1993.9631742zbMath0794.05124OpenAlexW1988435199MaRDI QIDQ4288050

Terri Wilhite Johnson, Peter J. Slater

Publication date: 21 April 1994

Published in: Quaestiones Mathematicae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/16073606.1993.9631742

zbMATH Keywords

NP-hardseries-parallel graphsmaximum independent setminimum total redundance

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items

A recurrence template for several parameters in series-parallel graphs

Cites Work

• Some simplified NP-complete graph problems
• A recurrence template for several parameters in series-parallel graphs
• A linear algorithm for the domination number of a series-parallel graph
• Graph-theoretic parameters concerning domination, independence, and irredundance
• Graph minors. II. Algorithmic aspects of tree-width
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item