Abstract
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.
M.M. Kanté is supported by the DORSO project, and L. Nourine by the DAG project, both of ”Agence Nationale Pour la Recherche”.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Araújo, J., Campos, V., Giroire, F., Nisse, N., Sampaio L., Soares, R.P.: On the hull number of some graph classes. Technical report (2011)
Bouchet, A.: Transforming trees by successive local complementations. J. Graph Theory 12(2), 195–207 (1988)
Chartrand, G., Fink, J.F., Zhang, P.: The hull number of an oriented graph. International Journal of Mathematics and Mathematical Sciences (36), 2265–2275 (2003)
Chvátal, V.: Antimatroids, betweenness, convexity. In: Cook, W.J., Lovász, L. (eds.) Research Trends in Combinatorial Optimization, pp. 57–64. Springer (2009)
Codd, E.F.: Further normalization of the data base relational model. In: Rustin, R. (ed.) Data Base Systems, pp. 33–64. Prentice Hall, Englewood Cliffs (1972)
Courcelle, B.: The monadic second-order logic of graphs XVI: Canonical graph decompositions. Logical Methods in Computer Science 2(2) (2006)
Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: a Language Theoretic Approach. Encyclopedia of Mathematics and its Applications, vol. 138. Cambridge University Press (2012)
Cunningham, W.H., Edmonds, J.: A combinatorial decomposition theory. Canadian Journal of Mathematics 32, 734–765 (1980)
Dahlhaus, E.: Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition. J. Algorithms 36(2), 205–240 (2000)
Diestel, R.: Graph Theory, 3rd edn. Springer (2005)
Dirac, G.A.: On rigid circuit graphs. Abhandlungen Aus Dem Mathematischen Seminare der Universität Hamburg 25(1-2), 71–76 (1961)
Dourado, M.C., Gimbel, J.G., Kratochvíl, J., Protti, F., Szwarcfiter, J.L.: On the computation of the hull number of a graph. Discrete Mathematics 309(18), 5668–5674 (2009)
Dourado, M.C., Protti, F., Rautenbach, D., Szwarcfiter, J.L.: On the hull number of triangle-free graphs. SIAM J. Discrete Math. 23(4), 2163–2172 (2010)
Dourado, M.C., Protti, F., Rautenbach, D., Szwarcfiter, J.L.: Some remarks on the geodetic number of a graph. Discrete Mathematics 310(4), 832–837 (2010)
Ekim, T., Erey, A., Heggernes, P., van ’t Hof, P., Meister, D.: Computing Minimum Geodetic Sets of Proper Interval Graphs. In: Fernández-Baca, D. (ed.) LATIN 2012. LNCS, vol. 7256, pp. 279–290. Springer, Heidelberg (2012)
Everett, M.G., Seidman, S.B.: The hull number of a graph. Discrete Mathematics 57(3), 217–223 (1985)
Fulkerson, D.R., Gross, O.A.: Incidence Matrices and Interval Graphs. Pacific J. Math. 15(3), 835–855 (1965)
Gavoille, C., Paul, C.: Distance labeling scheme and split decomposition. Discrete Mathematics 273(1-3), 115–130 (2003)
Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423–443 (2000)
Pelayo, I.M.: On convexity in graphs. Technical report (2004)
Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266–283 (1976)
Saiedian, H., Spencer, T.: An efficient algorithm to compute the candidate keys of a relational database schema. Comput. J. 39(2), 124–132 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kanté, M.M., Nourine, L. (2013). Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs. In: van Emde Boas, P., Groen, F.C.A., Italiano, G.F., Nawrocki, J., Sack, H. (eds) SOFSEM 2013: Theory and Practice of Computer Science. SOFSEM 2013. Lecture Notes in Computer Science, vol 7741. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35843-2_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-35843-2_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35842-5
Online ISBN: 978-3-642-35843-2
eBook Packages: Computer ScienceComputer Science (R0)