scientific article

Publication date: 1985

Full work available at URL: https://eudml.org/doc/17394

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (76)

Some aspects of the database resilience ⋮ Counting Subgraphs in Degenerate Graphs ⋮ Finding and counting small induced subgraphs efficiently ⋮ The monotone circuit complexity of Boolean functions ⋮ A Task-Scheduling Approach for Efficient Sparse Symmetric Matrix-Vector Multiplication on a GPU ⋮ Finding and counting cliques and independent sets in $r$-uniform hypergraphs ⋮ The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics ⋮ Strong computational lower bounds via parameterized complexity ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ Exact Weight Subgraphs and the k-Sum Conjecture ⋮ Pushdown reachability with constant treewidth ⋮ Parameterized circuit complexity and the $W$ hierarchy ⋮ Induced subgraph isomorphism: are some patterns substantially easier than others? ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Monotone arithmetic complexity of graph homomorphism polynomials ⋮ Sublinear separators, fragility and subexponential expansion ⋮ On low tree-depth decompositions ⋮ Grad and classes with bounded expansion. II: Algorithmic aspects ⋮ Counting Small Induced Subgraphs with Hereditary Properties ⋮ An improved algorithm for Klee's measure problem on fat boxes ⋮ On linear algebraic algorithms for the subgraph matching problem and its variants ⋮ Unnamed Item ⋮ Lower bounds for monotone $q$-multilinear Boolean circuits ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Finding small complete subgraphs efficiently ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Many Facets of Dualities ⋮ Are unique subgraphs not easier to find? ⋮ First-order definitions of subgraph isomorphism through the adjacency and order relations ⋮ A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques ⋮ Special issues on The satisfiability problem (pp. 1--244) including papers from the 1st workshop on satisfiability, Certosa di Pontignano, Italy, April 29--May 3, 1996 and Boolean functions (pp. 245--479) ⋮ Finding and counting small induced subgraphs efficiently ⋮ Method for quickly inferring the mechanisms of large-scale complex networks based on the census of subgraph concentrations ⋮ On the sum-max graph partitioning problem ⋮ Very large cliques are easy to detect ⋮ Efficient algorithms for the \textsc{max~$k$-vertex cover problem} ⋮ Efficient algorithms for subgraph listing ⋮ A fast deterministic detection of small pattern graphs in graphs without large cliques ⋮ Computing the number of induced copies of a fixed graph in a bounded degree graph ⋮ Finding and counting given length cycles ⋮ Advice classes of parametrized tractability ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ On first-order definitions of subgraph isomorphism properties ⋮ Open problems around exact algorithms ⋮ Unnamed Item ⋮ Detecting and Counting Small Pattern Graphs ⋮ Algebraic methods in the congested clique ⋮ On the complexity of fixed parameter clique and dominating set ⋮ Efficient algorithms for clique problems ⋮ New tools and connections for exponential-time approximation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized algorithms for module map problems ⋮ The complexity ecology of parameters: An illustration using bounded max leaf number ⋮ Counting Subgraphs in Relational Event Graphs ⋮ Beating treewidth for average-case subgraph isomorphism ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ Rare siblings speed-up deterministic detection and counting of small pattern graphs ⋮ Counting Answers to Existential Questions ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction ⋮ Improved simulation of nondeterministic Turing machines ⋮ A (slightly) faster algorithm for Klee's measure problem ⋮ Tight lower bounds for certain parameterized NP-hard problems ⋮ Logical complexity of induced subgraph isomorphism for certain families of graphs ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ Large clique is hard on average for resolution

This page was built for publication: