The Partial Inverse Minimum Connected Spanning Subgraph Problem with Given Cyclomatic Number

Zhe Heng Ding; Fang Zhu; Qin Wang

doi:10.4028/www.scientific.net/AMR.760-762.2114

Paper Titles

Design and Implementation of Object-Oriented Teaching Aid System Based on UML Language
p.2095

Design and Implementation of Network Topology Discovery System Based on OSPF
p.2100

Web-Based Interactive Visualization of Virtual Reality
p.2104

Research and Application of the Workshop Scheduling Algorithm Based on the Rules
p.2109

The Partial Inverse Minimum Connected Spanning Subgraph Problem with Given Cyclomatic Number
p.2114

The Application of Multi-Objective Particle Swarm Optimization in Economic Dispatch of Power System
p.2119

DWT Based Blind Watermark in Relational Database
p.2123

Use of Watermark in Educational Administration System
p.2129

Stability and Bifurcation Analysis in Leukopoiesis Models with Two Delays
p.2135

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 760-762The Partial Inverse Minimum Connected Spanning...

The Partial Inverse Minimum Connected Spanning Subgraph Problem with Given Cyclomatic Number

Abstract:

In this paper, we consider a partial inverse problem of minimum connected spanning subgraph with cyclomatic number . That is, given a subgraph, a cyclomatic number and a constraint that the edge weights can only decrease, we want to modify the edge weights as little as possible, so that there exists a minimum connected spanning subgraph with cyclomatic number and containing the given subgraph. For the case that the given subgraph is a connected subgraph with cyclomatic number , we solve the problem in polynomial time by contracting the subgraph. And when the given subgraph is a spanning tree, we solve the problem in polynomial time by using the MST algorithm.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 760-762)

Pages:

2114-2118

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.760-762.2114

Citation:

Cite this paper

Online since:

September 2013

Authors:

Zhe Heng Ding, Fang Zhu, Qin Wang

Keywords:

Cyclomatic Number, Minimum Connected Spanning Subgraph, MST Algorithm, Partial Inverse Problem

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] A. Dress, S. Grunewald, D. Stevanovic, Semiharmonic graphs with fixed cyclomatic number, Applied Mathematics Letters, 17: 623-629, (2004).

DOI: 10.1016/s0893-9659(04)90096-1

Google Scholar

[2] G.L. Chia, W. Hemakul, S. Singhun, Graphs with cyclomatic number two having panconnected square, Discrete Mathematics, 311: 850-855, (2011).

DOI: 10.1016/j.disc.2011.01.030

Google Scholar

[3] A.A. Dobrynin, L.S. Mel'nikov, Wiener index for graphs and their line graphs with arbitrary large cyclomatic numbers, Applied Mathematics Letters, 18: 307-312, (2005).

DOI: 10.1016/j.aml.2004.03.007

Google Scholar

[4] J. Harant, D. Rautenbach, P. Recht, F. Regen, Packing edge-disjoint cycles in graphs and the cyclomatic number, Discrete Mathematics, 310: 1456-1462, (2010).

DOI: 10.1016/j.disc.2009.07.017

Google Scholar

[5] L. Robert, S. Martin, Real flow number and the cycle rank of a graph, Journal of Graph Theory, 59 (1): 11-16, (2008).

Google Scholar

[6] M.C. Cai, C.W. Duin, X.G. Yang, J.Z. Zhang, The partial inverse minimum spanning tree problem when weight increase is forbidden. European Journal of Operational Research, 188: 348-353, (2008).

DOI: 10.1016/j.ejor.2007.04.031

Google Scholar