On Three Graph Layout Problems
David Muradian
Broschiertes Buch

On Three Graph Layout Problems

Versandfertig in 6-10 Tagen
19,99 €
inkl. MwSt.
PAYBACK Punkte
10 °P sammeln!
The bandwidth minimization problem for graphs was first stated in 1966 by Harper, where the problem was solved for hypercubes. Finding the bandwidth of an arbitrary graph is an NP-complete problem and it remains NP-complete for many simple structures, e.g. for cyclic caterpillars with hair length at most 1, graphs in which the removal of all pendant vertices results in a simple cycle. There are only few classes of graphs for which an efficient solution to the bandwidth problem is known. Classes of graphs whose bandwidth can be computed efficiently are butterflies, chain graphs, caterpillars wi...