On the complexity of finding a potential community

DOI10.1007/978-3-319-57586-5_8MaRDI QIDQ5283357zbMATH OpenOpenAlexFDO

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

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)

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 DE number 4200260

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• Complement reducible graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• On Syntactic versus Computational Views of Approximability
• Optimization, approximation, and complexity classes
• 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

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)