More Web Proxy on the site http://driver.im/

article

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

Authors:

Ante ăźUstić,

Abraham P. PunnenAuthors Info & Claims

Journal of Combinatorial Optimization, Volume 35, Issue 2

Pages 436 - 453

https://doi.org/10.1007/s10878-017-0184-3

Published: 01 February 2018 Publication History

Abstract

We investigate special cases of the quadratic minimum spanning tree problem (QMSTP) on a graph $$G=(V,E)$$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)$$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.

References

[1]

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

Digital Library

[2]

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

[3]

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

[4]

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

[5]

Çela E, Deineko VG, Woeginger GJ (2016) Linearizable special cases of the QAP. J Comb Optim 31:1269- 1279.

Digital Library

[6]

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

[7]

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

[8]

Custic A, Sokol V, Punnen AP, Bhattacharya B (2017) The bilinear assignment problem: complexity and polynomially solvable special cases. Math Program.

[9]

Custic A, Zhang R, Punnen AP (2016) The quadratic minimum spanning tree problem and its variations. Discrete Optim.

[10]

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

[11]

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

Digital Library

[12]

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

Digital Library

[13]

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

Digital Library

[14]

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-405.

Digital Library

[15]

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

Digital Library

[16]

Kabadi SN, Punnen AP (2011) An O(n⁴) algorithm for the QAP linearization problem. Math Oper Res 36:754-761.

Digital Library

[17]

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

Digital Library

[18]

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-428.

[19]

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

[20]

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-72.

Digital Library

[21]

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

[22]

Ö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-1773.

Digital Library

[23]

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

[24]

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-236.

[25]

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-379.

Digital Library

[26]

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-160.

[27]

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

[28]

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

[29]

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

[30]

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

Digital Library

[31]

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

Digital Library

[32]

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

Digital Library

[33]

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

Digital Library

Cited By

Çela EKlinz BLendl SWoeginger GWulf L(2023)A Linear Time Algorithm for Linearizing Quadratic and Higher-Order Shortest Path ProblemsInteger Programming and Combinatorial Optimization10.1007/978-3-031-32726-1_33(466-479)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-32726-1_33
Çela EKlinz BLendl SOrlin JWoeginger GWulf L(2021)Linearizable Special Cases of the Quadratic Shortest Path ProblemGraph-Theoretic Concepts in Computer Science10.1007/978-3-030-86838-3_19(245-256)Online publication date: 23-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-86838-3_19
de Meijer FSotirov R(2020)The quadratic cycle cover problem: special cases and efficient bounds Journal of Combinatorial Optimization10.1007/s10878-020-00547-739:4(1096-1128)Online publication date: 1-May-2020
https://dl.acm.org/doi/10.1007/s10878-020-00547-7

A characterization of linearizable instances of the quadratic minimum spanning tree problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

A Parallel Algorithm for the Degree-Constrained Minimum Spanning Tree Problem Using Nearest-Neighbor Chains
ISPAN '99: Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks

The Minimum Spanning Tree (MST) problem with an added constraint that no node in the spanning tree has the degree more than a specified integer d, is known as the Degree-Constrained MST (d-MST) problem. Since computing the d-MST is NP-hard for every d ...
A new algorithm for the minimum spanning tree verification problem

This paper proposes a new algorithm for the minimum spanning tree verification (MSTV) problem in undirected graphs. The MSTV problem is distinct from the minimum spanning tree construction problem. The above problems have been studied extensively, and ...
Minimum spanning tree with hop restrictions
Special issue: Twelfth annual ACM-SIAM symposium on discrete algorithms

Let U = (u_ij)_i,j=1ⁿ be a symmetric requirement matrix. Let d = (d_ij)_i,j=1ⁿ be a cost metric. A spanning tree T = (V, E_T) V = {1,2 ..... n} is feasible if for every pair of vertices v, w the v - w path in T contains at most u_vw, edges. We explore the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Combinatorial Optimization

Journal of Combinatorial Optimization Volume 35, Issue 2

February 2018

335 pages

ISSN:1382-6905

Issue’s Table of Contents

Copyright © Copyright © 2018 Springer Science+Business Media, LLC, part of Springer Nature.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 February 2018

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Çela EKlinz BLendl SWoeginger GWulf L(2023)A Linear Time Algorithm for Linearizing Quadratic and Higher-Order Shortest Path ProblemsInteger Programming and Combinatorial Optimization10.1007/978-3-031-32726-1_33(466-479)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-32726-1_33
Çela EKlinz BLendl SOrlin JWoeginger GWulf L(2021)Linearizable Special Cases of the Quadratic Shortest Path ProblemGraph-Theoretic Concepts in Computer Science10.1007/978-3-030-86838-3_19(245-256)Online publication date: 23-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-86838-3_19
de Meijer FSotirov R(2020)The quadratic cycle cover problem: special cases and efficient bounds Journal of Combinatorial Optimization10.1007/s10878-020-00547-739:4(1096-1128)Online publication date: 1-May-2020
https://dl.acm.org/doi/10.1007/s10878-020-00547-7

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents