On the relation of strong triadic closure and cluster deletion

DOI10.1007/978-3-030-00256-5_20zbMath1435.68234arXiv1803.00807OpenAlexW2789464506WikidataQ127365021 ScholiaQ127365021MaRDI QIDQ5915591

Niels Grüttemeier, Christian Komusiewicz

Publication date: 22 November 2018

Published in: Algorithmica, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.00807

zbMATH Keywords

social networksfixed-parameter algorithmsgraph classeskernelization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Social networks; opinion dynamics (91D30) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (12)

Destroying Bicolored $P_3$s by Deleting Few Edges ⋮ Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis ⋮ Parameterized aspects of strong subgraph closure ⋮ Structural parameterization of cluster deletion ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ FPT and kernelization algorithms for the induced tree problem ⋮ On the relation of strong triadic closure and cluster deletion ⋮ Unnamed Item ⋮ Cluster deletion on interval graphs and split related graphs ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ A new approximate cluster deletion algorithm for diamond-free graphs ⋮ (Sub)linear kernels for edge modification problems toward structured graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• The cluster deletion problem for cographs
• Kernel bounds for disjoint cycles and disjoint paths
• Cluster editing with locally bounded modifications
• A more effective linear kernelization for cluster editing
• Paw-free graphs
• Two classes of perfect graphs
• Gallai graphs and anti-Gallai graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Cluster graph modification problems
• Even faster parameterized cluster deletion and cluster editing
• Applying modular decomposition to parameterized cluster editing problems
• Fixed-parameter algorithms for maximum-profit facility location under matroid constraints
• The NP-Completeness of Edge-Coloring
• Graph Classes: A Survey
• Kernelization Lower Bounds by Cross-Composition
• Parameterized Algorithms
• On the relation of strong triadic closure and cluster deletion
• Strong triadic closure in cographs and graphs of low maximum degree
• Your rugby mates don't need to know your colleagues: triadic closure with edge colors

This page was built for publication: On the relation of strong triadic closure and cluster deletion