scientific article; zbMATH DE number 480527

MaRDI QIDQ4274209zbMATH OpenFDO

Authors Gerhard J. Woeginger

Publication date 3 January 1994

zbMATH Keywords

cographsconnected configurationsfast approximation algorithminterval graphsNP-completeplanerectilinear gridssplit graphstreesundirected graphs

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 841593
• Computing regions decomposable into m stars
• Max-min partitioning of grid graphs into connected components
• Algorithms for Computing the Maximum Weight Region Decomposable into Elementary Shapes
• Approximation algorithms for NP-complete problems on planar graphs

Cited in

(3)

• The computational complexity of the k-minimum spanning tree problem in graded matrices
• Local search algorithms for the \(k\)-cardinality tree problem.
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4274209)