Approximating the maximum sharing problem
Authors: 
Amitabh Chaudhary, Danny Z. Chen, 
Rudolf Fleischer, 
Xiaobo S. Hu, Jian Li, Michael T. Niemier, Zhiyi Xie, Hong ZhuAuthors Info & Claims
Pages 52 - 63
Abstract
In the maximum sharing problem (MS), we want to compute a set of (non-simple) paths in an undirected bipartite graph covering as many nodes as possible of the first node layer of the graph, with the constraint that all paths have both endpoints in the second node layer and no node in that layer is covered more than once. MS is equivalent to the node-duplication based crossing elimination problem (NDCE) that arises in the design of molecular quantum-dot cellular automata (QCA) circuits and the physical synthesis of BDD based regular circuit structures in VLSI design. We show that MS is NP-hard, present a polynomial-time 1.5-approximation algorithm, and show that MS cannot be approximated with a factor better than 740/739 unless P = NP.
References
[1]
Antonelli, D.A., Chen, D.Z., Dysart, T.J., Hu, X.S., Khang, A.B., Kogge, P.M., Murphy, R.C., Niemier, M.T.: Quantum-dot cellular automata (QCA) circuit partitioning: problem modeling and solutions. In: DAC'04. Proc. 41st ACM/IEEE Design Automation Conf., pp. 363-368. IEEE Computer Society Press, Los Alamitos (2004)
[2]
Berman, P., Karpinski, M.: 8/7-approximation algorithm for (1, 2)-TSP. In: SODA'06. Proc. 17th Annual ACM-SIAM Symp. on Discrete Algorithms, pp. 641-648. ACM Press, New York (2006)
[3]
Cao, A., Koh, C.-K.: Non-crossing ordered BDD for physical synthesis of regular circuit structure. In: Proc. International Workshop on Logic and Synthesis, pp. 200-206 (2003)
[4]
Chaudhary, A., Chen, D.Z., Hu, X.S., Niemier, M.T., Ravinchandran, R., Whitton, K.M.: Eliminating wire crossings for molecular quantum-dot cellular automata implementation. In: Proc. of IEEE/ACM International Conference on Computer-Aided Design, pp. 565-571. ACM Press, New York (2005)
[5]
Chen, D.Z., Fleischer, R., Li, J., Xie, Z., Zhu, H.: On approximating the maximum simple sharing problem. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol. 4288, pp. 547-556. Springer, Heidelberg (2006)
[6]
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Englewood Cliffs (1998)
[7]
Eades, P., Whitesides, S.: Drawing graphs in two layers. Theor. Comput. Sci. 131, 361-374 (1994)
[8]
Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11(4), 379-403 (1994)
[9]
Edmonds, J.: Paths, trees, and flowers. Canadian Journal of Mathematics 17, 449-467 (1965)
[10]
Engebretsen, L., Karpinski, M.: TSP with bounded metrics. Journal of Computer and System Sciences 72(4), 509-546 (2006)
[11]
Finocchi, I.: Layered Drawings of Graphs with Crossing Constraints. In: Proc. 9th Annual International Computing and Combinatorics Conference, pp. 357-367 (2001)
[12]
Gabow, H.N.: Data Structures for Weighted Matching and Nearest Common Ancestors with Linking. In: SODA'90. Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 434-443. ACM Press, New York (1990)
[13]
Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods 4(3), 312-316 (1983)
[14]
Lengauer, T.: Combinatorial Algorithms for Integrated Circuit Layout. Wiley, Chichester (1990)
[15]
Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Mathematics of Operations Research 18(1), 1-11 (1993)
[16]
Tougaw, P.D., Lent, C.S.: Logical devices implemented using quantum cellular automata. J. of App. Phys. 75, 1818 (1994)
[17]
Waterman, M.S., Griggs, J.R.: Interval graphs and maps of DNA. Bull. Math. Biol. 48(2), 189-195 (1986)
- Approximating the maximum sharing problem
Recommendations
Maximum domination problem
CATS 2011: Proceedings of the Seventeenth Computing on The Australasian Theory Symposium - Volume 119We consider new variants of the vertex/edge domination problems on graphs. A vertex is said to dominate itself and its all adjacent vertices, and similarly an edge is said to dominate itself and its all adjacent edges Given an input graph G = (V, E) and ...
Maximum domination problem
CATS '11: Proceedings of the Seventeenth Computing: The Australasian Theory Symposium - Volume 119We consider new variants of the vertex/edge domination problems on graphs. A vertex is said to dominate itself and its all adjacent vertices, and similarly an edge is said to dominate itself and its all adjacent edges Given an input graph G = (V, E) and ...
Approximating Maximum Subgraphs without Short Cycles
We study approximation algorithms, integrality gaps, and hardness of approximation of two problems related to cycles of “small” length $k$ in a given (undirected) graph. The instance for these problems consists of a graph $G=(V,E)$ and an integer $k$. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- AARMS: Atlantic Assoc for Research in the Mathematical Sciences
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 15 August 2007
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Nov 2024