On the Complexity of Finding a Potential Community

DOI10.1007/978-3-319-57586-5_8zbMath1486.68122OpenAlexW2607123191MaRDI QIDQ5283357

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

complexityalgorithmcombinatorial optimizationindependent setinapproximability

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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Cites Work

• Complement reducible graphs
• 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
• A partial k-arboretum of graphs with bounded treewidth
• Efficient algorithms for interval graphs and circular-arc graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• On Syntactic versus Computational Views of Approximability
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Complexity of Finding a Potential Community