Color-coding
From MaRDI portal
Publication:4369883
DOI10.1145/210332.210337zbMath0885.68116OpenAlexW2296148711WikidataQ56639265 ScholiaQ56639265MaRDI QIDQ4369883
Noga Alon, Uri Zwick, Raphael Yuster
Publication date: 28 January 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/210332.210337
Related Items
A randomized algorithm for long directed cycle ⋮ On finding rainbow and colorful paths ⋮ An approximation algorithm for the longest cycle problem in solid grid graphs ⋮ Looking at the stars ⋮ On the ordered list subgraph embedding problems ⋮ Parameterizing role coloring on forests ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Fast exact algorithms using Hadamard product of polynomials ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ Finding disjoint paths on edge-colored graphs: more tractability results ⋮ Parameterized and approximation algorithms for finding two disjoint matchings ⋮ Parameterized tractability of the maximum-duo preservation string mapping problem ⋮ Solving linear equations parameterized by Hamming weight ⋮ Deterministic parameterized algorithms for the graph motif problem ⋮ Parameterized approximation algorithms for packing problems ⋮ Parameterized complexity and approximation issues for the colorful components problems ⋮ Formally verified algorithms for upper-bounding state space diameters ⋮ Finding monotone paths in edge-ordered graphs ⋮ On the rainbow connectivity of graphs: complexity and FPT algorithms ⋮ The density maximization problem in graphs ⋮ Chain minors are FPT ⋮ Parameterized complexity of superstring problems ⋮ Finding approximate and constrained motifs in graphs ⋮ Kernel and fast algorithm for dense triplet inconsistency ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Parameterized complexity of max-lifetime target coverage in wireless sensor networks ⋮ Parameterized maximum path coloring ⋮ Kernel bounds for path and cycle problems ⋮ Parameterized complexity of connected even/odd subgraph problems ⋮ On the negative cost girth problem in planar networks ⋮ Interval scheduling and colorful independent sets ⋮ Variants of constrained longest common subsequence ⋮ Scheduling and fixed-parameter tractability ⋮ On low tree-depth decompositions ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Improved approximation bounds for the minimum rainbow subgraph problem ⋮ A shortest cycle for each vertex of a graph ⋮ New results for the longest haplotype reconstruction problem ⋮ Parameterized random complexity ⋮ Parameterized complexity of even/odd subgraph problems ⋮ Quasi-hamiltonian paths in semicomplete multipartite digraphs ⋮ Finding and counting vertex-colored subtrees ⋮ Faster algorithms for finding and counting subgraphs ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ Are unique subgraphs not easier to find? ⋮ Stable assignment with couples: parameterized complexity and local search ⋮ Paths of bounded length and their cuts: parameterized complexity and algorithms ⋮ Lower bounds on kernelization ⋮ Confronting intractability via parameters ⋮ Randomised enumeration of small witnesses using a decision oracle ⋮ On the parameterized complexity of vertex cover and edge cover with connectivity constraints ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ Maximum disjoint paths on edge-colored graphs: approximability and tractability ⋮ Restricted and swap common superstring: a multivariate algorithmic perspective ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ Quell ⋮ Finding and counting given length cycles ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ Graph editing to a given degree sequence ⋮ Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs ⋮ Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits ⋮ Parity check matrices and product representations of squares ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Campaign management under approval-driven voting rules ⋮ Parameterized algorithms for weighted matching and packing problems ⋮ Complexity of Grundy coloring and its variants ⋮ Algorithm engineering for color-coding with applications to signaling pathway detection ⋮ Faster fixed-parameter tractable algorithms for matching and packing problems ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs ⋮ Fixed-parameter tractability of satisfying beyond the number of variables ⋮ Complexity issues for the sandwich homogeneous set problem ⋮ Complexity issues in vertex-colored graph pattern matching ⋮ Multivariate complexity analysis of Swap Bribery ⋮ Fast minor testing in planar graphs ⋮ Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs ⋮ A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families ⋮ A trichotomy for regular simple path queries on graphs ⋮ Algebraic methods in the congested clique ⋮ Efficient algorithms for clique problems ⋮ Finding paths of length \(k\) in \(O^{*}(2^k)\) time ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ Efficient approximation algorithms for shortest cycles in undirected graphs ⋮ Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem ⋮ Towards better models of externalities in sponsored search auctions ⋮ On the parameterized complexity of multiple-interval graph problems ⋮ The complexity of nonrepetitive coloring ⋮ Computing small partial coverings ⋮ Learning large-alphabet and analog circuits with value injection queries ⋮ Generalized rainbow connectivity of graphs ⋮ Detecting directed 4-cycles still faster ⋮ An approximation algorithm for computing longest paths. ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ On problems without polynomial kernels ⋮ Linear time algorithms for finding a dominating set of fixed size in degenerated graphs ⋮ On counting 3-D matchings of size \(k\) ⋮ A faster parameterized algorithm for set packing ⋮ On the complexity of database queries ⋮ Parameterized complexity of the anchored \(k\)-core problem for directed graphs ⋮ Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Almost Optimal Cover-Free Families ⋮ Spotting Trees with Few Leaves ⋮ Algorithms for Regular Tree Grammar Network Search and Their Application to Mining Human-Viral Infection Patterns ⋮ Parameterized Complexity of $$(A,\ell )$$-Path Packing ⋮ Counting Subgraphs in Degenerate Graphs ⋮ Collaborating with Hans: Some Remaining Wonderments ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices ⋮ Parameterized Parallel Computing and First-Order Logic ⋮ Simultaneously load balancing for every p-norm, with reassignments ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ Mixing Color Coding-Related Techniques ⋮ Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks ⋮ Improved Upper Bounds for Partial Vertex Cover ⋮ Edge-Disjoint Packing of Stars and Cycles ⋮ Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem ⋮ Exact Weight Subgraphs and the k-Sum Conjecture ⋮ Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis ⋮ On the parameterized complexity of the acyclic matching problem ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs ⋮ Find subtrees of specified weight and cycles of specified length in linear time ⋮ Inapproximability of shortest paths on perfect matching polytopes ⋮ Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters ⋮ Parameterised counting in logspace ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ On the approximability of path and cycle problems in arc-dependent networks ⋮ Almost optimal query algorithm for hitting set using a subset query ⋮ Detours in directed graphs ⋮ Parameterized Algorithms and Hardness Results for Some Graph Motif Problems ⋮ Packing arc-disjoint cycles in oriented graphs ⋮ Parameterised and fine-grained subgraph counting, modulo 2 ⋮ On the power of threshold-based algorithms for detecting cycles in the \textsc{CONGEST} model ⋮ On the power of threshold-based algorithms for detecting cycles in the CONGEST model ⋮ A branch‐and‐price‐and‐cut algorithm for the truck‐drone routing problem with simultaneously delivery and pickup ⋮ Parallel connectivity in edge-colored complete graphs: complexity results ⋮ Improved Parameterized Algorithms for Weighted 3-Set Packing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Parameterized Complexity of Motion Planning for Snake-Like Robots ⋮ Going Far from Degeneracy ⋮ Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding ⋮ Genomic Scaffold Filling: A Progress Report ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ Model checking existential logic on partially ordered sets ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ The Maximum Binary Tree Problem. ⋮ The Parameterized Complexity of Finding Point Sets with Hereditary Properties ⋮ Diverse Pairs of Matchings ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Extended formulations in combinatorial optimization ⋮ On the difficulty of finding walks of length k ⋮ On the $AC^0$ Complexity of Subgraph Isomorphism ⋮ Graph Editing to a Given Degree Sequence ⋮ Balanced paths in acyclic networks: Tractable cases and related approaches ⋮ Unnamed Item ⋮ Extended formulations in combinatorial optimization ⋮ Slightly Superexponential Parameterized Problems ⋮ Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated ⋮ Parameterized algorithms for module map problems ⋮ 1.61-approximation for min-power strong connectivity with two power levels ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ On the complexity of finding internally vertex-disjoint long directed paths ⋮ Approximately Counting Embeddings into Random Graphs ⋮ Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs ⋮ Unnamed Item ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ The Maximum Colorful Arborescence problem parameterized by the structure of its color hierarchy graph ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ Maximum Motif Problem in Vertex-Colored Graphs ⋮ On the Descriptive Complexity of Color Coding ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ Decomposition of Map Graphs with Applications. ⋮ Packing Arc-Disjoint Cycles in Tournaments ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Unnamed Item ⋮ Balanced Hashing, Color Coding and Approximate Counting ⋮ Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms ⋮ The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex ⋮ Fine-Grained Complexity of Rainbow Coloring and its Variants. ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Balanced substructures in bicolored graphs ⋮ Subgraph nomination: query by example subgraph retrieval in networks ⋮ Unit read-once refutations for systems of difference constraints ⋮ Methods for determining cycles of a specific length in undirected graphs with edge weights ⋮ A polynomial excluded-minor approximation of treedepth ⋮ A note on algebraic techniques for subgraph detection ⋮ Kernel Bounds for Path and Cycle Problems ⋮ Spotting Trees with Few Leaves ⋮ Edge-disjoint packing of stars and cycles ⋮ Fast Output-Sensitive Matrix Multiplication ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ Studies in Computational Aspects of Voting ⋮ FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Parameterized complexity of reconfiguration of atoms ⋮ The parameterized complexity of unique coverage and its variants ⋮ On the fine-grained parameterized complexity of partial scheduling to minimize the makespan ⋮ Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets ⋮ Narrow sieves for parameterized paths and packings ⋮ Networks of polynomial pieces with application to the analysis of point clouds and images ⋮ The balanced connected subgraph problem for geometric intersection graphs ⋮ QUBO formulations of the longest path problem ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ A multivariate framework for weighted FPT algorithms ⋮ Answering conjunctive queries with inequalities ⋮ Parameterized analysis and crossing minimization problems ⋮ Packing arc-disjoint cycles in tournaments ⋮ Deterministic Subgraph Detection in Broadcast CONGEST. ⋮ Lower Bounds for Subgraph Detection in the CONGEST Model ⋮ Parameterized complexity of secluded connectivity problems ⋮ The parameterized space complexity of embedding along a path ⋮ Computing Hitting Set Kernels By AC^0-Circuits ⋮ Evaluation and Enumeration Problems for Regular Path Queries ⋮ Improved Parameterized Algorithms for Network Query Problems ⋮ Parameterized edge Hamiltonicity ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ Mind the gap! ⋮ Improved parameterized algorithms for network query problems ⋮ The structural complexity landscape of finding balance-fair shortest paths ⋮ On the tractability of finding disjoint clubs in a network ⋮ Grad and classes with bounded expansion. II: Algorithmic aspects ⋮ An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem ⋮ Lengths of words accepted by nondeterministic finite automata ⋮ Parameterised temporal exploration problems ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ First-order definitions of subgraph isomorphism through the adjacency and order relations ⋮ Contracting graphs to paths and trees ⋮ Parameterized complexity of Eulerian deletion problems ⋮ A faster FPT algorithm for bipartite contraction ⋮ Parameterized low-rank binary matrix approximation ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Parameterized \(k\)-clustering: tractability island ⋮ Finding Approximate and Constrained Motifs in Graphs ⋮ Clustering with Local Restrictions ⋮ Open problems around exact algorithms ⋮ Algorithms for topology-free and alignment network queries ⋮ Unnamed Item ⋮ The parameterised complexity of counting connected subgraphs and graph motifs ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ Partial information network queries ⋮ Parameterized complexity of \textsc{maximum edge colorable subgraph} ⋮ Faster deterministic parameterized algorithm for \(k\)-path ⋮ Representative families for matroid intersections, with applications to location, packing, and covering problems ⋮ Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem ⋮ Parameterized complexity of a coupled-task scheduling problem ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ Fixed-parameter algorithms for scaffold filling ⋮ The maximum binary tree problem ⋮ Beating treewidth for average-case subgraph isomorphism ⋮ New and improved algorithms for unordered tree inclusion ⋮ Fine-grained complexity of rainbow coloring and its variants ⋮ An approximation algorithm for the longest path problem in solid grid graphs ⋮ The Budgeted Unique Coverage Problem and Color-Coding ⋮ A Slice Theoretic Approach for Embedding Problems on Digraphs ⋮ Parameterized complexity of small weight automorphisms and isomorphisms ⋮ Parameterized Complexity of Eulerian Deletion Problems ⋮ Improved distance queries and cycle counting by Frobenius normal form ⋮ Univariate ideal membership parameterized by rank, degree, and number of generators ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review ⋮ Two edge-disjoint paths with length constraints ⋮ Parameterized algorithms and complexity for the traveling purchaser problem and its variants ⋮ Parameterized complexity of multi-node hubs ⋮ On the complexity of approximately matching a string to a directed graph ⋮ Finding colorful paths in temporal graphs ⋮ Tournaments and Semicomplete Digraphs ⋮ Colored cut games ⋮ Parameterized complexity of maximum edge colorable subgraph ⋮ Comparing incomplete sequences via longest common subsequence ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Unique subgraphs are not easier to find ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ Editing to a graph of given degrees ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems ⋮ To close is easier than to open: dual parameterization to \(k\)-median ⋮ Parameterized complexity of \((A,\ell)\)-path packing
