Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs. (English) Zbl 1303.05195
van Emde Boas, Peter (ed.) et al., SOFSEM 2013: theory and practice of computer science. 39th international conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 26–31, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-35842-5/pbk). Lecture Notes in Computer Science 7741, 268-279 (2013).
Summary: We give linear and polynomial time algorithms for computing a minimum hull-set in distance-hereditary and chordal graphs respectively. Prior to our result a polynomial time algorithm was only known for sub-classes of considered graph classes. Our techniques allow us to give at the same time a linear time algorithm for computing a minimum geodetic set in distance-hereditary graphs.
For the entire collection see [Zbl 1298.68036].
For the entire collection see [Zbl 1298.68036].
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C35 | Extremal problems in graph theory |
| 68Q25 | Analysis of algorithms and problem complexity |
