scientific article
From MaRDI portal
Publication:3002818
DOI10.4086/toc.2010.v006a005zbMath1213.68316OpenAlexW2150004999MaRDI QIDQ3002818
Publication date: 24 May 2011
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2010.v006a005
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (68)
Structural decompositions for problems with global constraints ⋮ Tree-Depth and the Formula Complexity of Subgraph Isomorphism ⋮ Lower Bounds for the Graph Homomorphism Problem ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ On Directed Steiner Trees with Multiple Roots ⋮ Target Set Selection in Dense Graph Classes ⋮ Known Algorithms for Edge Clique Cover are Probably Optimal ⋮ Parameterized complexity of reconfiguration of atoms ⋮ Strong partial clones and the time complexity of SAT problems ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ On the fine-grained parameterized complexity of partial scheduling to minimize the makespan ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ The parameterized complexity of local search for TSP, more refined ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ Monotone arithmetic complexity of graph homomorphism polynomials ⋮ On the parameterized complexity of compact set packing ⋮ Parameterized complexity of envy-free resource allocation in social networks ⋮ Solving infinite-domain CSPs using the patchwork property ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ On the optimality of pseudo-polynomial algorithms for integer programming ⋮ Unnamed Item ⋮ Fixing improper colorings of graphs ⋮ Extended formulation for CSP that is compact for instances of bounded treewidth ⋮ Unnamed Item ⋮ Preference swaps for the stable matching problem ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ The complexity of routing problems in forbidden-transition graphs and edge-colored graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the algorithmic effectiveness of digraph decompositions and complexity measures ⋮ On the Optimality of Pseudo-polynomial Algorithms for Integer Programming ⋮ The Parameterized Complexity of Finding Point Sets with Hereditary Properties ⋮ A tight lower bound for planar Steiner orientation ⋮ Tractable structures for constraint satisfaction with truth tables ⋮ On the $AC^0$ Complexity of Subgraph Isomorphism ⋮ The inverse Voronoi problem in graphs. I: Hardness ⋮ The treewidth of proofs ⋮ Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms ⋮ Routing with congestion in acyclic digraphs ⋮ Unnamed Item ⋮ Complexity of token swapping and its variants ⋮ The treewidth of line graphs ⋮ Parameterized counting of partially injective homomorphisms ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ Fractal dimension and lower bounds for geometric problems ⋮ Beating treewidth for average-case subgraph isomorphism ⋮ Finding and counting permutations via CSPs ⋮ On tree width, bramble size, and expansion ⋮ Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ Unnamed Item ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Counting Answers to Existential Questions ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Target set selection parameterized by vertex cover and more ⋮ Searching and inferring colorful topological motifs in vertex-colored graphs ⋮ On the Complexity of Bounded Context Switching. ⋮ Tight Lower Bounds for List Edge Coloring ⋮ Treewidth of the Line Graph of a Complete Graph ⋮ Parameterized complexity of list coloring and max coloring ⋮ Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ Pure Nash equilibria in graphical games and treewidth ⋮ Unnamed Item ⋮ On the impact of treewidth in the computational complexity of freezing dynamics ⋮ New limits of treewidth-based tractability in optimization ⋮ Backdoors to q-Horn
This page was built for publication:
