Finding a potential community in networks

DOI10.1016/J.TCS.2018.10.011MaRDI QIDQ1737592zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cites work

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

Cited in

(2)

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

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)