nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Extended Spanning Star Forest Problems

verfasst von : Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, Dirk Oliver Theis

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We continue the investigation proposed in [COCOA 2016, Weller, Chateau, Giroudeau, König and Pollet “On Residual Approximation in Solution Extension Problems”] about the study of extended problems. In this context, a partial feasible solution is given in advance and the goal is to extend this partial solution. In this paper, we focus on the edge-weighted spanning star forest problem for both minimization and maximization versions. The goal here is to find a vertex partition of an edge-weighted complete graph into disjoint non-trivial stars and the value of a solution is given by the sum of the edge-weights of the stars. We propose NP-hardness, parameterized complexity, positive and negative approximation results.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel New Insights for Power Edge Set Problem

Nächstes Kapitel Faster and Enhanced Inclusion-Minimal Cograph Completion

In this case, it is also required that some vertices are forbidden.

Agatz, N.A.H., Erera, A.L., Savelsbergh, M.W.P., Wang, X.: Optimization for dynamic ride-sharing: a review. Eur. J. Oper. Res. 223(2), 295–303 (2012)CrossRefMATH

Agra, A., Cardoso, D., Cerfeira, O., Rocha, E.: A spanning star forest model for the diversity problem in automobile industry. In: ECCO XVIII, Minsk (2005)

Athanassopoulos, S., Caragiannis, I., Kaklamanis, C., Papaioannou, E.: Energy-efficient communication in multi-interface wireless networks. In: Královič, R., Niwiński, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 102–111. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03816-7_10 CrossRef

Böckenhauer, H.-J., Hromkovic, J., Klasing, R., Seibert, S., Unger, W.: Approximation algorithms for the TSP with sharpened triangle inequality. Inf. Process. Lett. 75(3), 133–138 (2000)CrossRefMATHMathSciNet

Chakrabarty, D., Goel, G.: On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. SIAM J. Comput. 39(6), 2189–2211 (2010)CrossRefMATHMathSciNet

Chen, N., Engelberg, R., Nguyen, C.T., Raghavendra, P., Rudra, A., Singh, G.: Improved approximation algorithms for the spanning star forest problem. Algorithmica 65(3), 498–516 (2013)CrossRefMATHMathSciNet

Delbot, F., Laforest, C., Phan, R.: Graphs with forbidden and required vertices. In: ALGOTEL 2015-17emes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications Jun 2015, Beaune (2015). https://hal.archives-ouvertes.fr/hal-01148233

Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013). https://doi.org/10.1007/978-1-4471-5559-1 CrossRefMATH

Fotakis, D., Gourvès, L., Monnot, J.: Conference program design with single-peaked and single-crossing preferences. In: Cai, Y., Vetta, A. (eds.) WINE 2016. LNCS, vol. 10123, pp. 221–235. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-54110-4_16 CrossRef

10.

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)MATH

11.

Hartman, I.B.-A., Keren, D., Dbai, A.A., Cohen, E., Knapen, L., Yasar, A.-U.-H., Janssens, D.: Theory and practice in large carpooling problems. In: Shakshuki, E.M., Yasar, A.-U.-H. (eds.) Proceedings of the 5th International Conference on Ambient Systems, Networks and Technologies (ANT 2014), The 4th International Conference on Sustainable Energy Information Technology (SEIT-2014), Hasselt, 2–5 June 2014, vol. 32. Procedia Computer Science, pp. 339–347. Elsevier (2014)

12.

He, J., Liang, H.: Improved approximation for spanning star forest in dense graphs. J. Comb. Optim. 25(2), 255–264 (2013)CrossRefMATHMathSciNet

13.

Kutiel, G.: Approximation algorithms for the maximum carpool matching problem. In: Weil, P. (ed.) CSR 2017. LNCS, vol. 10304, pp. 206–216. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-58747-9_19 CrossRef

14.

Nguyen, C.T., Shen, J., Hou, M., Sheng, L., Miller, W., Zhang, L.: Approximating the spanning star forest problem and its application to genomic sequence alignment. SIAM J. Comput. 38(3), 946–962 (2008)CrossRefMATHMathSciNet

15.

Nguyen, V.H.: The maximum weight spanning star forest problem on cactus graphs. Discrete Math. Algorithms Appl. 7(2), 1550018 (2015)CrossRefMATHMathSciNet

16.

Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2003)MATH

17.

Tuza, Z.: Graph colorings with local constraints - a survey. Discussiones Mathematicae Graph Theory 17(2), 161–228 (1997)CrossRefMATHMathSciNet

18.

Weller, M., Chateau, A., Giroudeau, R., König, J.-C., Pollet, V.: On residual approximation in solution extension problems. In: Chan, T.-H.H., Li, M., Wang, L. (eds.) COCOA 2016. LNCS, vol. 10043, pp. 463–476. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48749-6_34 CrossRef

Titel: Extended Spanning Star Forest Problems
verfasst von: Kaveh Khoshkhah
Mehdi Khosravian Ghadikolaei
Jérôme Monnot
Dirk Oliver Theis
Verlag: Springer International Publishing
Buch: Combinatorial Optimization and Applications
Print ISBN: 978-3-319-71149-2

Electronic ISBN: 978-3-319-71150-8

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-71150-8_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"