scientific article; zbMATH DE number 1261820
From MaRDI portal
Publication:4231923
zbMath0938.68932MaRDI QIDQ4231923
Leonard J. Schulman, Aravind Srinivasan, Moni Naor
Publication date: 26 April 2000
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (only showing first 100 items - show all)
On the parameterized complexity of the acyclic matching problem ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Packing arc-disjoint cycles in oriented graphs ⋮ Balanced substructures in bicolored graphs ⋮ Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ Diverse Pairs of Matchings ⋮ Parameterized Complexity of Directed Spanner Problems. ⋮ Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs ⋮ Exact learning of DNF formulas using DNF hypotheses ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ A randomized algorithm for long directed cycle ⋮ On the ordered list subgraph embedding problems ⋮ Almost Optimal Cover-Free Families ⋮ Parameterizing role coloring on forests ⋮ Fast exact algorithms using Hadamard product of polynomials ⋮ Parameterized and approximation algorithms for finding two disjoint matchings ⋮ The cell probe complexity of succinct data structures ⋮ On the Fine-Grained Complexity of Rainbow Coloring ⋮ Mixing Color Coding-Related Techniques ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ Finding Two Edge-Disjoint Paths with Length Constraints ⋮ Deterministic constructions of high-dimensional sets with small dispersion ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Parameterized algorithms for non-separating trees and branchings in digraphs ⋮ Parameterized complexity of directed spanner problems ⋮ On some network design problems with degree constraints ⋮ Exact learning of juntas from membership queries ⋮ Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem ⋮ Finding monotone paths in edge-ordered graphs ⋮ Parameterized algorithms for graph partitioning problems ⋮ Parameterized complexity of secluded connectivity problems ⋮ Chain minors are FPT ⋮ Parameterized complexity of superstring problems ⋮ Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ On testing monomials in multivariate polynomials ⋮ Linear Time Constructions of Some $$d$$-Restriction Problems ⋮ Matching and weighted \(P_2\)-packing: algorithms and kernels ⋮ A simple algorithm for learning O(log n)-term DNF ⋮ Unnamed Item ⋮ Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters ⋮ Parameterized complexity of finding connected induced subgraphs ⋮ Improved Parameterized Algorithms for Weighted 3-Set Packing ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem ⋮ Parameterized random complexity ⋮ Multicut Is FPT ⋮ Parameterized complexity of even/odd subgraph problems ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ The complexity of routing problems in forbidden-transition graphs and edge-colored graphs ⋮ Contracting graphs to paths and trees ⋮ Parameterized complexity of Eulerian deletion problems ⋮ The Parameterized Complexity of Motion Planning for Snake-Like Robots ⋮ Going Far from Degeneracy ⋮ A faster FPT algorithm for bipartite contraction ⋮ Packing paths: recycling saves time ⋮ Parameterized low-rank binary matrix approximation ⋮ Confronting intractability via parameters ⋮ Parameterized \(k\)-clustering: tractability island ⋮ Randomised enumeration of small witnesses using a decision oracle ⋮ Unnamed Item ⋮ Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding ⋮ On the parameterized complexity of vertex cover and edge cover with connectivity constraints ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ Identification of partial disjunction, parity, and threshold functions ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ Graph editing to a given degree sequence ⋮ Clustering with Local Restrictions ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Campaign management under approval-driven voting rules ⋮ Threshold and Majority Group Testing ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ On the parameterized complexity of contraction to generalization of trees ⋮ Improved deterministic algorithms for weighted matching and packing problems ⋮ Graph Editing to a Given Degree Sequence ⋮ Slightly Superexponential Parameterized Problems ⋮ Efficient algorithms for clique problems ⋮ Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fréchet distance between a line and avatar point set ⋮ Complexity of independency and cliquy trees ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs ⋮ Fine-grained complexity of rainbow coloring and its variants ⋮ Attribute-efficient learning in query and mistake-bound models ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ On the Complexity of Computing the k-restricted Edge-connectivity of a Graph ⋮ Editing to Connected F-Degree Graph ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas ⋮ Balanced Hashing, Color Coding and Approximate Counting ⋮ Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
This page was built for publication:
