Advanced search
Publication Cover
Optimization
A Journal of Mathematical Programming and Operations Research
Volume 68, 2019 - Issue 10: 7th German Polish Conference on Optimization - Methods and Applications
Submit an article Journal homepage
240
Views
2
CrossRef citations to date
0
Altmetric
Articles

An improved flow-based formulation and reduction principles for the minimum connectivity inference problem

Muhammad Abid Dar Faculty of Mathematics, Institute of Numerical Mathematics, Technische Universität Dresden , Dresden, Germany.View further author information
,
Andreas Fischer Faculty of Mathematics, Institute of Numerical Mathematics, Technische Universität Dresden , Dresden, Germany.Correspondence[email protected]
ORCID Iconhttps://orcid.org/0000-0001-7703-1655View further author information
ORCID Icon,
John Martinovic Faculty of Mathematics, Institute of Numerical Mathematics, Technische Universität Dresden , Dresden, Germany.View further author information
&
Guntram Scheithauer Faculty of Mathematics, Institute of Numerical Mathematics, Technische Universität Dresden , Dresden, Germany.ORCID Iconhttps://orcid.org/0000-0003-4061-3357View further author information
ORCID Icon
Pages 1963-1983 | Received 28 Oct 2017, Accepted 11 Apr 2018, Published online: 30 Apr 2018

References

  • Chockler G , Melamed R , Tock Y , Vitenberg R . Constructing scalable overlays for pub-sub with many topics. In: Gupta I , editor. Proceedings of the twenty-sixth annual ACM symposium on principles of distributed computing. New York (NY): ACM; 2007. p. 109–118.
  • Du DZ , Miller Z . Matroids and subset interconnection design. SIAM J Discrete Math. 1988;1(4):416–424.
  • Du DZ , Chen YM . Placement of valves in vacuum systems. Commun Electric Light Source Technol. 1976;4:22–28. Chinese.
  • Du DZ . Curriculum Vitae of Ding-Zuh Du; 2017 [cited 25 Jul 2017]. Available from: http://www.utdallas.edu/dxd056000/
  • Du DZ . An optimization problem on graphs. Discrete Appl Math. 1986;14(1):101–104.
  • Prisner E . Two algorithms for the subset interconnection design problem. Networks. 1992;22(4):385–395.
  • Chen C , Jacobsen HA , Vitenberg R . Algorithms based on divide and conquer for topic-based publish/subscribe overlay design. IEEE/ACM Trans Netw. 2016;24(1):422–436.
  • Chen J , Komusiewicz C , Niedermeier R , Sorge M , Suchý O , Weller M . Polynomial-time data reduction for the subset interconnection design problem. SIAM J Discrete Math. 2015;29(1):1–25.
  • Hosoda J , Hromkovič J , Izumi T , Ono H , Steinová M , Wada K . On the approximability and hardness of minimum topic connected overlay and its special instances. Theor Comput Sci. 2012;429:144–154.
  • Fan H , Hundt C , Wu YL , Ernst J . Algorithms and implementation for interconnection graph problem. In: Yang B , Du DZ , Wang CA , editors. Combinatorial optimization and applications. Vol. 5165, Lecture notes in computer science. Berlin: Springer; 2008. p. 201–210.
  • Angluin D , Aspnes J , Reyzin L . Inferring social networks from outbreaks. In: International conference on algorithmic learning theory. Vol. 6331, Lecture notes in computer science. Berlin: Springer; 2010. p. 104–118.
  • Agarwal D , Araujo JCS , Caillouet C , Cazalst F , Coudert D , Pérennes S Connectivity inference in mass spectrometry based structure determination. In: European symposium on algorithms. Vol. 8125, Lecture notes in computer science. Berlin: Springer; 2013. p. 289–300.
  • Agarwal D , Caillouet C , Coudert D , Cazals F . Unveiling contacts within macromolecular assemblies by solving minimum weight connectivity inference (MWC) problems. Mol Cell Proteomics. 2015;14(8):2274–2284.
  • Du DZ , Kelley DF . On complexity of subset interconnection designs. J Global Optim. 1995;6(2):193–205.
  • Chwatal AM , Raidl GR . Solving the minimum label spanning tree problem by mathematical programming techniques. Adv Oper Res. 2011;2011:38. Available from: http://dx.doi.org/10.1155/2011/143732.
  • Magnanti TL , Wolsey LA . Network routing. In: Ball MO , Magnanti TL , Monma BL , Nemhauser G , editors. Handbooks in operations research and management science. Vol. 7. Amsterdam: Elsevier; 1995. p. 503–615.
  • Hopcroft J , Tarjan R . Algorithm 447: efficient algorithms for graph manipulation. Commun ACM. 1973;16(6):372–378.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.