Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
From MaRDI portal
Publication:3506940
DOI10.1007/978-3-540-69068-9_6zbMath1143.68501WikidataQ57359911 ScholiaQ57359911MaRDI QIDQ3506940
Nadja Betzler, Christian Komusiewicz, Michael R. Fellows, Rolf Niedermeier
Publication date: 17 June 2008
Published in: Combinatorial Pattern Matching (Search for Journal in Brave)
Full work available at URL: http://espace.cdu.edu.au/view/cdu:9643
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W20: Randomized algorithms
Related Items
Unnamed Item, Constrained multilinear detection and generalized graph motifs, Confronting intractability via parameters, Complexity issues in vertex-colored graph pattern matching, Upper and lower bounds for finding connected motifs in vertex-colored graphs, Finding and counting vertex-colored subtrees, Algorithms for topology-free and alignment network queries, The parameterised complexity of counting connected subgraphs and graph motifs, Some results on more flexible versions of Graph Motif, Improved parameterized algorithms for network query problems, Colourful components in \(k\)-caterpillars and planar graphs, Improved Parameterized Algorithms for Network Query Problems, Finding Approximate and Constrained Motifs in Graphs, Unnamed Item, Maximum Motif Problem in Vertex-Colored Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Perfect Code is \(W[1\)-complete]
- Fourier meets M\"{o}bius: fast subset convolution
- Color-coding
- Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
- Depth-First Search and Linear Graph Algorithms