Assessing the Computational Complexity of Multi-layer Subgraph Detection

DOI10.1007/978-3-319-57586-5_12zbMath1486.68126arXiv1604.07724OpenAlexW2963760377MaRDI QIDQ5283362

Hendrik Molter, Christian Komusiewicz, Stefan Kratsch, Manuel Sorge, Rolf Niedermeier, Robert Bredereck

Publication date: 21 July 2017

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Approximating multistage matching problems

Uses Software

• GenLouvain

Cites Work

• Unnamed Item
• Graph factors and factorization: 1985--2003: a survey
• On the parameterized complexity of multiple-interval graph problems
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parameterized complexity of finding subgraphs with hereditary properties.
• Algorithmic graph theory and perfect graphs
• Competitive graph searches
• Dual Connectedness of Edge-Bicolored Graphs and Beyond
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
• Graph Classes: A Survey
• Simultaneous Feedback Vertex Set: A Parameterized Perspective
• The Parameterized Complexity of k-B<scp>iclique</scp>
• Parameterized Algorithms

This page was built for publication: Assessing the Computational Complexity of Multi-layer Subgraph Detection