Finding a potential community in networks

DOI10.1016/J.TCS.2018.10.011zbMATH Open1421.68064OpenAlexW2898526288WikidataQ129077865 ScholiaQ129077865MaRDI QIDQ1737592FDOQ1737592

Authors: Cristina Bazgan, Thomas Pontoizeau, Zsolt Tuza 

Publication date: 23 April 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://real.mtak.hu/105505/1/Bazgan-Pontoi-Tuza-Finding-a-potential-community.pdf

Recommendations

• On the complexity of finding a potential community
• Structural and algorithmic properties of 2-community structures
• New insight into 2-community structures in graphs with applications in social networks
• A general view on computing communities
• Detecting strong cliques

zbMATH Keywords

graphalgorithmcomplexityinapproximabilityindependent set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Graph clustering
• Networks, crowds and markets. Reasoning about a highly connected world.
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Complement reducible graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Every planar map is four colorable. I: Discharging
• A partial k-arboretum of graphs with bounded treewidth
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Graph structure and monadic second-order logic. A language-theoretic approach
• Efficient algorithms for interval graphs and circular-arc graphs
• Some simplified NP-complete graph problems
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• A Linear Recognition Algorithm for Cographs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• A simple linear time algorithm for cograph recognition
• On Syntactic versus Computational Views of Approximability
• Triangles, 4-Cycles and Parameterized (In-)Tractability

Cited In (2)

• New insight into 2-community structures in graphs with applications in social networks
• On the complexity of finding a potential community

This page was built for publication: Finding a potential community in networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1737592)