Document Open Access Logo

A Polynomial-Delay Algorithm for Enumerating Connectors Under Various Connectivity Conditions

Authors Kazuya Haraguchi, Hiroshi Nagamochi

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2019.3.pdf
  • Filesize: 0.58 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph enumeration
Keywords
  • Graph with itemsets
  • Enumeration
  • Polynomial-delay algorithms
  • Connectors

Metrics

Abstract

We are given an instance (G,I,sigma) with a graph G=(V,E), a set I of items, and a function sigma:V -> 2^I. For a subset X of V, let G[X] denote the subgraph induced from G by X, and I_sigma(X) denote the common item set over X. A subset X of V such that G[X] is connected is called a connector if, for any vertex v in V\X, G[X cup {v}] is not connected or I_sigma(X cup {v}) is a proper subset of I_sigma(X).
In this paper, we present the first polynomial-delay algorithm for enumerating all connectors. For this, we first extend the problem of enumerating connectors to a general setting so that the connectivity condition on X in G can be specified in a more flexible way. We next design a new algorithm for enumerating all solutions in the general setting, which leads to a polynomial-delay algorithm for enumerating all connectors for several connectivity conditions on X in G, such as the biconnectivity of G[X] or the k-edge-connectivity among vertices in X in G.

Cite As Get BibTex

Kazuya Haraguchi and Hiroshi Nagamochi. A Polynomial-Delay Algorithm for Enumerating Connectors Under Various Connectivity Conditions. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ISAAC.2019.3

Author Details

Kazuya Haraguchi
  • Otaru University of Commerce, Midori 3-5-21, Otaru, Hokkaido 047-8501, Japan
Hiroshi Nagamochi
  • Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, Japan

References

  1. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Optimization, volume 1 of Handbooks in Management Science and Operations Research, chapter Network Flows (IV), pages 211-369. North-Holland, 1989. Google Scholar
  2. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs, NJ, 1993. Google Scholar
  3. David Avis and Komei Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65(1):21-46, 1996. Google Scholar
  4. Kazuya Haraguchi, Yusuke Momoi, Aleksandar Shurbevski, and Hiroshi Nagamochi. COOMA: a components overlaid mining algorithm for enumerating connected subgraphs with common itemsets. Journal of Graph Algorithms and Applications, 23(2):434-458, 2019. URL: https://doi.org/10.7155/jgaa.00497.
  5. Akihiro Inokuchi, Takashi Washio, and Hiroshi Motoda. An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data. In Djamel A. Zighed, Jan Komorowski, and Jan Żytkow, editors, Principles of Data Mining and Knowledge Discovery, pages 13-23, 2000. URL: https://doi.org/10.1007/3-540-45372-5_2.
  6. Shin-ichi Nakano and Takeaki Uno. Efficient Generation of Rooted Trees. Technical Report NII-2003-005E, National Institute of Informatics, July 2003. Google Scholar
  7. Zeev Nutov. Listing minimal edge-covers of intersecting families with applications to connectivity problems. Discrete Applied Mathamatics, 157(1):112-117, 2009. URL: https://doi.org/10.1016/j.dam.2008.04.026.
  8. Shingo Okuno. Parallelization of Graph Mining using Backtrack Search Algorithm. PhD thesis, Kyoto University, 2017. URL: https://doi.org/10.14989/doctor.k20518.
  9. Shingo Okuno, Tasuku Hiraishi, Hiroshi Nakashima, Masahiro Yasugi, and Jun Sese. Parallelization of Extracting Connected Subgraphs with Common Itemsets. Information and Media Technologies, 9(3):233-250, 2014. URL: https://doi.org/10.11185/imt.9.233.
  10. Shingo Okuno, Tasuku Hiraishi, Hiroshi Nakashima, Masahiro Yasugi, and Jun Sese. Reducing Redundant Search in Parallel Graph Mining Using Exceptions. In 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pages 328-337, 2016. URL: https://doi.org/10.1109/IPDPSW.2016.136.
  11. Mio Seki and Jun Sese. Identification of active biological networks and common expression conditions. In 2008 8th IEEE International Conference on BioInformatics and BioEngineering, pages 1-6, 2008. Google Scholar
  12. Jun Sese, Mio Seki, and Mutsumi Fukuzaki. Mining Networks with Shared Items. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management (CIKM '10), pages 1681-1684, 2010. Google Scholar
  13. Emanuel Sperner. Ein Satz über Untermengen einer endlichen Menge. Mathematische Zeitschrift, 27(1):544-548, 1928. URL: https://doi.org/10.1007/BF01171114.
  14. Takeaki Uno. Two general methods to reduce delay and change of enumeration algorithms. Technical Report NII-2003-004E, National Institute of Informatics, April 2003. Google Scholar
  15. Xifeng Yan and Jiawei Han. gSpan: Graph-based substructure pattern mining. In Proceedings of 2002 IEEE International Conference on Data Mining (ICDM '02), pages 721-724, 2002. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact