Graph-modeled data clustering: Fixed-parameter algorithms for clique generation

DOI10.1007/3-540-44849-7_17MaRDI QIDQ4437501zbMATH OpenFDO

Authors Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier

Publication date 2 December 2003

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

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2653/26530108.htm

zbMATH Keywords

data clusteringedge modification problemsexact algorithmsfixed-parameter tractabilityNP-complete problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Graph-modeled data clustering: Exact algorithms for clique generation
• Alternative parameterizations for cluster editing
• Cluster graph modification problems
• Cluster graph modification problems
• Cluster editing with locally bounded modifications

Cited in

(40)

• Cluster editing problem for points on the real line: a polynomial time algorithm
• Cluster graph modification problems
• Even faster parameterized cluster deletion and cluster editing
• Clustering with local restrictions
• Branch-and-price for \(p\)-cluster editing
• Even better fixed-parameter algorithms for bicluster editing
• Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
• Cluster deletion revisited
• Clustering with partial information
• Applying modular decomposition to parameterized cluster editing problems
• Parameterized algorithms for min-max 2-cluster editing
• Clustering with qualitative information
• Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
• Editing simple graphs
• Alternative parameterizations for cluster editing
• Fixed-Parameter Tractable Generalizations of Cluster Editing
• Applying Modular Decomposition to Parameterized Bicluster Editing
• Fixed-Parameter Algorithms for Graph-Modeled Date Clustering
• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Editing
• The cluster deletion problem for cographs
• Cluster graph modification problems
• Graph-based data clustering with overlaps
• Lower bounds on kernelization
• On parameterized and kernelization algorithms for the hierarchical clustering problem
• Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions
• Branch-and-cut approaches for p-cluster editing
• On 2-clubs in graph-based data clustering: theory and algorithm engineering
• Incompressibility of H-free edge modification problems: towards a dichotomy
• An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion
• Structural parameterization of cluster deletion
• Cutting a tree with subgraph complementation is hard, except for some small trees
• Cutting a tree with subgraph complementation is hard, except for some small trees
• \( \gamma \)-clustering problems: classical and parametrized complexity
• Improved kernelization and fixed-parameter algorithms for bicluster editing
• Structural parameterization of cluster deletion
• Correcting a graph into a linegraph minimizing Hamming distance edition is NP-complete and FPT by treewidth
• Cluster editing on cographs and related classes
• Graph-modeled data clustering: Exact algorithms for clique generation
• Fixed-parameter enumerability of cluster editing and related problems
• Fixed-parameter algorithms for cluster vertex deletion

This page was built for publication: Graph-modeled data clustering: Fixed-parameter algorithms for clique generation

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