Your rugby mates don't need to know your colleagues: triadic closure with edge colors

DOI10.1016/j.jcss.2021.03.001zbMath1477.68210OpenAlexW3138189744MaRDI QIDQ5918315

Niels Grüttemeier, Christian Komusiewicz, Manuel Sorge, Laurent Bulteau

Publication date: 30 June 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2021.03.001

zbMATH Keywords

edge coloringfixed-parameter tractabilityexponential time hypothesiskernelizationsocial network analysis

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Social networks; opinion dynamics (91D30) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• A \(2k\) kernel for the cluster editing problem
• A fast algorithm for equitable coloring
• Finding odd cycle transversals.
• Improved upper bounds for vertex cover
• A simplified NP-complete satisfiability problem
• A more effective linear kernelization for cluster editing
• Two classes of perfect graphs
• Gallai graphs and anti-Gallai graphs
• Which problems have strongly exponential complexity?
• Parameterized aspects of strong subgraph closure
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Applying modular decomposition to parameterized cluster editing problems
• Fixed-parameter algorithms for maximum-profit facility location under matroid constraints
• Parametrized complexity theory.
• On the Fine-Grained Complexity of Rainbow Coloring
• The NP-Completeness of Edge-Coloring
• NP completeness of finding the chromatic index of regular graphs
• Compression via Matroids
• Kernelization Lower Bounds Through Colors and IDs
• Kernelization Lower Bounds by Cross-Composition
• Reducibility among Combinatorial Problems
• Fine-Grained Complexity of Rainbow Coloring and its Variants.
• Tight Lower Bounds for List Edge Coloring
• Parameterized Algorithms
• Transitiv orientierbare Graphen
• On the relation of strong triadic closure and cluster deletion
• Strong triadic closure in cographs and graphs of low maximum degree