Induced bipartite subgraphs of maximal vertex cardinality are an essential
concept for the analysis of graphs. Yet, discovering them in large graphs is
known to be computationally hard. Therefore, we consider in this work a weaker
notion of this problem, where we discard the maximality constraint in favor of
inclusion maximality. Thus, we aim to discover locally maximal bipartite
subgraphs. For this, we present three heuristic approaches to extract such
subgraphs and compare their results to the solutions of the global problem. For
the latter, we employ the algorithmic strength of fast SAT-solvers. Our three
proposed heuristics are based on a greedy strategy, a simulated annealing
approach, and a genetic algorithm, respectively. We evaluate all four
algorithms with respect to their time requirement and the vertex cardinality of
the discovered bipartite subgraphs on several benchmark datasets
%0 Generic
%1 durrschnabel2022discovering
%A Dürrschnabel, Dominik
%A Hanika, Tom
%A Stumme, Gerd
%D 2022
%K 2022 bipartite induced_subgraphs itegpub myown
%T Discovering Locally Maximal Bipartite Subgraphs
%U http://arxiv.org/abs/2211.10446
%X Induced bipartite subgraphs of maximal vertex cardinality are an essential
concept for the analysis of graphs. Yet, discovering them in large graphs is
known to be computationally hard. Therefore, we consider in this work a weaker
notion of this problem, where we discard the maximality constraint in favor of
inclusion maximality. Thus, we aim to discover locally maximal bipartite
subgraphs. For this, we present three heuristic approaches to extract such
subgraphs and compare their results to the solutions of the global problem. For
the latter, we employ the algorithmic strength of fast SAT-solvers. Our three
proposed heuristics are based on a greedy strategy, a simulated annealing
approach, and a genetic algorithm, respectively. We evaluate all four
algorithms with respect to their time requirement and the vertex cardinality of
the discovered bipartite subgraphs on several benchmark datasets
@misc{durrschnabel2022discovering,
abstract = {Induced bipartite subgraphs of maximal vertex cardinality are an essential
concept for the analysis of graphs. Yet, discovering them in large graphs is
known to be computationally hard. Therefore, we consider in this work a weaker
notion of this problem, where we discard the maximality constraint in favor of
inclusion maximality. Thus, we aim to discover locally maximal bipartite
subgraphs. For this, we present three heuristic approaches to extract such
subgraphs and compare their results to the solutions of the global problem. For
the latter, we employ the algorithmic strength of fast SAT-solvers. Our three
proposed heuristics are based on a greedy strategy, a simulated annealing
approach, and a genetic algorithm, respectively. We evaluate all four
algorithms with respect to their time requirement and the vertex cardinality of
the discovered bipartite subgraphs on several benchmark datasets},
added-at = {2023-01-04T19:21:55.000+0100},
author = {Dürrschnabel, Dominik and Hanika, Tom and Stumme, Gerd},
biburl = {https://www.bibsonomy.org/bibtex/2fc9773815aa51c5aa3f70f440314e48d/duerrschnabel},
interhash = {8c9d10c8d7b45a9fbc91b990d72b619d},
intrahash = {fc9773815aa51c5aa3f70f440314e48d},
keywords = {2022 bipartite induced_subgraphs itegpub myown},
note = {cite arxiv:2211.10446Comment: 12 pages, 3 figures, 3 tables},
timestamp = {2024-05-21T10:22:55.000+0200},
title = {Discovering Locally Maximal Bipartite Subgraphs},
url = {http://arxiv.org/abs/2211.10446},
year = 2022
}