Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
On the Complexity of Minimizing the Total Calibration Cost Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Maximum Edge Bicliques in Tree Convex Bipartite Graphs

Authors : Hao Chen, Tian Liu

Published in: Frontiers in Algorithmics

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We show that the computational complexity of the maximum edge biclique (MEB) problem in tree convex bipartite graphs depends on the associated trees. That is, MEB is \(\mathcal {NP}\)-complete for star convex bipartite graphs, but polynomial time solvable for tree convex bipartite graphs whose associated trees have a constant number of leaves. In particular, MEB is polynomial time solvable for triad convex bipartite graphs. Moreover, we show that the same algorithm strategy may not work for circular convex bipartite graphs, and triad convex bipartite graphs are incomparable with respect to chordal bipartite graphs.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter On Computational Aspects of Greedy Partitioning of Graphs
next chapter Complete Submodularity Characterization in the Comparative Independent Cascade Model
Literature
1.
Acuña, V., Ferreira, C.E., Freire, A.S., Moreno, E.: Solving the maximum edge biclique packing problem on unbalanced bipartite graphs. Discret. Appl. Math. 164, 2–12 (2014)MathSciNetCrossRefMATH
2.
Alexe, G., Alexe, S., Crama, Y., Foldes, S., Hammer, P.L., Simeone, B.: Consensus algorithms for the generation of all maximal bicliques. Discret. Appl. Math. 145(1), 11–21 (2004)MathSciNetCrossRefMATH
3.
Ambühl, C., Mastrolilli, M., Svensson, O.: Inapproximability resullts for maximum edge biclique, minimum linear arrangement, and sparse cut. SIAM J. Comput. 40(2), 567–596 (2011)MathSciNetCrossRefMATH
4.
Brandstad, A., Le, V.B., Spinrad, J.P.: Graph Classes - A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)CrossRef
5.
Chen, H., Lei, Z., Liu, T., Tang, Z., Wang, C., Xu, K.: Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs. J. Comb. Optim. 32(1), 95–110 (2016)MathSciNetCrossRefMATH
6.
Dawande, M., Keskinocak, P., Swaminathan, J.M., Tayur, S.: On bipartite and multipartite clique problems. J. Algorithms 41, 388–403 (2001)MathSciNetCrossRefMATH
7.
Dias, V.M., de Figueiredo, C.M., Szwarcfiter, J.L.: Generating bicliques of a graph in lexicographic order. Theoret. Comput. Sci. 337(1C3), 240–248 (2005)MathSciNetCrossRefMATH
8.
Dias, V.M., de Figueiredo, C.M., Szwarcfiter, J.L.: On the generation of bicliques of a graph. Discret. Appl. Math. 155(14), 1826–1832 (2007)MathSciNetCrossRefMATH
9.
Feige, U.: Relations between average case complexity and approximation complexity. In: Proceedings of STOC 2002, pp. 534–543 (2002)
10.
Gély, A., Nourine, L., Sadi, B.: Enumeration aspects of maximal cliques and bicliques. Discret. Appl. Math. 157(7), 1447–1459 (2009)MathSciNetCrossRefMATH
11.
12.
Goerdt, A., Lanka, A.: An approximation hardness result for bipartite clique. Electronic Colloquium on Computation Complexity TR2004-048 (2004)
13.
Grover, F.: Maximum matching in a convex bipartite graph. Nav. Res. Logist. Q. 14, 313–316 (1967)CrossRef
14.
Jiang, W., Liu, T., Ren, T., Xu, K.: Two hardness results on feedback vertex sets. In: Atallah, M., Li, X.-Y., Zhu, B. (eds.) FAW-AAIM 2011. LNCS, vol. 6681, pp. 233–243. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-21204-8_​26 CrossRef
15.
Jiang, W., Liu, T., Wang, C., Xu, K.: Feedback vertex sets on restricted bipartite graphs. Theoret. Comput. Sci. 507, 41–51 (2013)MathSciNetCrossRefMATH
16.
Jiang, W., Liu, T., Xu, K.: Tractable feedback vertex sets in restricted bipartite graphs. In: Wang, W., Zhu, X., Du, D.-Z. (eds.) COCOA 2011. LNCS, vol. 6831, pp. 424–434. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-22616-8_​33 CrossRef
17.
Liang, Y.D., Blum, N.: Circular convex bipartite graphs: maximum matching and Hamiltonian circuits. Inf. Process. Lett. 56, 215–219 (1995)MathSciNetCrossRefMATH
18.
Liu, T.: Restricted bipartite graphs: comparison and hardness results. In: Gu, Q., Hell, P., Yang, B. (eds.) AAIM 2014. LNCS, vol. 8546, pp. 241–252. Springer, Cham (2014). doi:10.​1007/​978-3-319-07956-1_​22
19.
20.
21.
22.
Lu, M., Liu, T., Xu, K.: Independent domination: reductions from circular- and triad-convex bipartite graphs to convex bipartite graphs. In: Fellows, M., Tan, X., Zhu, B. (eds.) AAIM/FAW -2013. LNCS, vol. 7924, pp. 142–152. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38756-2_​16 CrossRef
23.
Lu, M., Liu, T., Tong, W., Lin, G., Xu, K.: Set cover, set packing and hitting set for tree convex and tree-like set systems. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) TAMC 2014. LNCS, vol. 8402, pp. 248–258. Springer, Cham (2014). doi:10.​1007/​978-3-319-06089-7_​17 CrossRef
24.
Lu, Z., Liu, T., Xu, K.: Tractable connected domination for restricted bipartite graphs (extended abstract). In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 721–728. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38768-5_​65 CrossRef
25.
26.
Nussbaum, D., Pu, S., Sack, J., Uno, T., Zarrabi-Zadeh, H.: Finding maximum edge bicliques in convex bipartite graphs. Algorithmica 64, 311–325 (2012)MathSciNetCrossRefMATH
27.
28.
Pandey, A., Panda, B.S.: Domination in some subclasses of bipartite graphs. In: Ganguly, S., Krishnamurti, R. (eds.) CALDAM 2015. LNCS, vol. 8959, pp. 169–180. Springer, Cham (2015). doi:10.​1007/​978-3-319-14974-5_​17
29.
Song, Y., Liu, T., Xu, K.: Independent domination on tree convex bipartite graphs. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM/FAW -2012. LNCS, vol. 7285, pp. 129–138. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-29700-7_​12 CrossRef
30.
Wang, C., Chen, H., Lei, Z., Tang, Z., Liu, T., Xu, K.: Tree convex bipartite graphs: \(\cal{NP}\)-complete domination, hamiltonicity and treewidth. In: Chen, J., Hopcroft, J.E., Wang, J. (eds.) FAW 2014. LNCS, vol. 8497, pp. 252–263. Springer, Cham (2014). doi:10.​1007/​978-3-319-08016-1_​23 CrossRef
31.
Metadata
Title
Maximum Edge Bicliques in Tree Convex Bipartite Graphs
Authors
Hao Chen
Tian Liu
Copyright Year
2017
Book
Frontiers in Algorithmics

Print ISBN: 978-3-319-59604-4

Electronic ISBN: 978-3-319-59605-1

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-59605-1_5

Premium Partner

    Image Credits