On the complexity of finding a potential community

DOI10.1007/978-3-319-57586-5_8zbMATH Open1486.68122OpenAlexW2607123191MaRDI QIDQ5283357FDOQ5283357

Authors: Thomas Pontoizeau, Zsolt Tuza, Cristina Bazgan 

Publication date: 21 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://real.mtak.hu/74285/1/FindComm_Bazgan_et_al_u.pdf

Recommendations

• Finding a potential community in networks
• Structural and algorithmic properties of 2-community structures
• The maximum independent union of cliques problem: complexity and exact approaches
• scientific article; zbMATH DE number 3872703
• scientific article

zbMATH Keywords

combinatorial optimizationalgorithmcomplexityinapproximabilityindependent set

Mathematics Subject Classification ID

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

Cites Work

• Optimization, approximation, and complexity classes
• Complement reducible graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A partial k-arboretum of graphs with bounded treewidth
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Efficient algorithms for interval graphs and circular-arc graphs
• Some simplified NP-complete graph problems
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• On Syntactic versus Computational Views of Approximability

Cited In (1)

• Finding a potential community in networks

This page was built for publication: On the complexity of finding a potential community

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