nach oben

Journal of Combinatorial Optimization

Erschienen in:

11.10.2017

A characterization of linearizable instances of the quadratic minimum spanning tree problem

verfasst von: Ante Ćustić, Abraham P. Punnen

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2018

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We investigate special cases of the quadratic minimum spanning tree problem (QMSTP) on a graph \(G=(V,E)\) that can be solved as a linear minimum spanning tree problem. We give a characterization of such problems when G is a complete graph, which is the standard case in the QMSTP literature. We extend our characterization to a larger class of graphs that include complete bipartite graphs and cactuses, among others. Our characterization can be verified in \(O(|E|^2)\) time. In the case of complete graphs and when the cost matrix is given in factored form, we show that our characterization can be verified in O(|E|) time. Related open problems are also indicated.

Vorheriger Artikel Algorithm complexity of neighborhood total domination and -graphs

Nächster Artikel Upper bounds for adjacent vertex-distinguishing edge coloring

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 "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

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

Adams W, Waddell L (2014) Linear programming insights into solvable cases of the quadratic assignment problem. Discret Optim 14:46–60MathSciNetCrossRefMATH

Assad A, Xu W (1992) The quadratic minimum spanning tree problem. Naval Res Logist 39:399–417MathSciNetCrossRefMATH

Bookhold I (1990) A contribution to quadratic assignment problems. Optimization 21:933–943MathSciNetCrossRefMATH

Buchheim C, Klein L (2014) Combinatorial optimization with one quadratic term: spanning trees and forests. Discret Appl Math 177:34–52MathSciNetCrossRefMATH

Çela E, Deĭneko VG, Woeginger GJ (2016) Linearizable special cases of the QAP. J Comb Optim 31:1269–1279MathSciNetCrossRefMATH

Cordone R, Passeri G (2012) Solving the quadratic minimum spanning tree problem. Appl Math Comput 218:11597–11612MathSciNetMATH

Ćustić A (2014) Efficiently solvable special cases of multidimensional assignment problems. Ph.D. thesis, TU Graz

Ćustić A, Sokol V, Punnen AP, Bhattacharya B (2017) The bilinear assignment problem: complexity and polynomially solvable special cases. Math Program. doi:10.1007/s10107-017-1111-1

Ćustić A, Zhang R, Punnen AP (2016) The quadratic minimum spanning tree problem and its variations. Discrete Optim. doi:10.1016/j.disopt.2017.09.003

Darmann A, Pferschy U, Schauer S, Woeginger GJ (2011) Paths, trees and matchings under disjunctive constraints. Discret Appl Math 159:1726–1735MathSciNetCrossRefMATH

Fischer A, Fischer F (2013) Complete description for the spanning tree problem with one linearised quadratic term. Oper Res Lett 41:701–705MathSciNetCrossRefMATH

Fu ZH, Hao JK (2015) A three-phase search approach for the quadratic minimum spanning tree problem. Eng Appl Artif Intell 46:113–130CrossRef

Gao J, Lu M (2005) Fuzzy quadratic minimum spanning tree problem. Appl Math Comput 164:773–788MathSciNetMATH

Goyal V, Genc-Kaya L, Ravi R (2011) An FPTAS for minimizing the product of two non-negative linear cost functions. Math Program 126:401–405MathSciNetCrossRefMATH

Hopcroft J, Tarjan R (1973) Efficient algorithm for graph manipulation. Commun ACM 16:372–378CrossRef

Kabadi SN, Punnen AP (2011) An \(O(n^4)\) algorithm for the QAP linearization problem. Math Oper Res 36:754–761MathSciNetCrossRefMATH

Kern W, Woeginger GJ (2007) Quadratic programming and combinatorial minimum weight product problems. Math Program 110:641–649MathSciNetCrossRefMATH

Lozano M, Glover F, Garcia-Martinez C, Rodriguez JF, Marti R (2014) Tabu search with strategic oscillation for the quadratic minimum spanning tree. IIE Trans 46:414–428CrossRef

Maia SMDM, Goldbarg EFG, Goldbarg MC (2013) On the biobjective adjacent only quadratic spanning tree problem. Electron Notes Discret Math 41:535–542CrossRef

Maia SMDM, Goldbarg EFG, Goldbarg MC (2014) Evolutionary algorithms for the bi-objective adjacent only quadratic spanning tree. Int J Innovative Comput Appl 6:63–72CrossRef

Mittal S, Schulz AS (2013) An FPTAS for optimizing a class of low-rank functions over a polytope. Math Program 141:103–120MathSciNetCrossRefMATH

Öncan T, Punnen AP (2010) The quadratic minimum spanning tree probelm: a lower bounding procedure and an efficient search algorithm. Comput Oper Res 37:1762–1773MathSciNetCrossRefMATH

Palubeckis G, Rubliauskas D, Targamadzė A (2010) Metaheuristic approaches for the quadratic minimum spanning tree problem. Inf Technol Control 29:257–268

Pereira DL, Gendreau M, da Cunha AS (2013) Stronger lower bounds for the quadratic minimum spanning tree problem with adjacency costs. Electron Notes Discret Math 41:229–236CrossRef

Pereira DL, Gendreau M, da Cunha AS (2015) Branch-and-cut and Branch-and-cut-and-price algorithms for the adjacent only quadratic minimum spanning tree problem. Networks 65:367–379MathSciNetCrossRef

Pereira DL, Gendreau M, da Cunha AS (2015) Lower bounds and exact algorithms for the quadratic minimum spanning tree problem. Comput Oper Res 63:149–160MathSciNetCrossRefMATH

Punnen AP, Kabadi SN (2013) A linear time algorithm for the Koopmans-Beckman QAP linearization and related problems. Discret Optim 10:200–209CrossRef

Punnen AP (2001) Combinatorial optimization with multiplicative objective function. Int J Oper Quant Manag 7:205–209

Punnen AP, Woods B (2017) A characterizations of linearizable instances of the quadratic travelling salesman problem. arXiv:1708.07217v2 [cs.DM]

Rostami B, Malucelli F (2015) Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation. Comput Oper Res 64:178–188MathSciNetCrossRefMATH

Sundar S, Singh A (2010) A swarm intelligence approach to the quadratic minimum spanning tree problem. Inf Sci 180:3182–3191MathSciNetCrossRef

Zhang R, Kabadi SN, Punnen AP (2011) The minimum spanning tree problem with conflict constraints and its variations. Discret Optim 8:191–205MathSciNetCrossRefMATH

Zhou G, Gen M (1998) An effective genetic algorithm approach to the quadratic minimum spanning tree problem. Comput Oper Res 25:229–237MathSciNetCrossRefMATH

Titel: A characterization of linearizable instances of the quadratic minimum spanning tree problem
verfasst von: Ante Ćustić
Abraham P. Punnen
Publikationsdatum: 11.10.2017
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2018
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-017-0184-3

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 "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2018

List-edge-coloring of planar graphs without 6-cycles with three chords

The connected disk covering problem

A local search approximation algorithm for the uniform capacitated k-facility location problem

Bin packing game with a price of anarchy of

Computational aspects of greedy partitioning of graphs

Properly colored trails, paths, and bridges

Premium Partner