Distributed complexity of P_k-freeness: decision and certification
From MaRDI portal
Distributed complexity of \(P k\)-freeness: decision and certification
Cites work
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- 4-colorability of P₆-free graphs
- A meta-theorem for distributed certification
- A subquadratic certification scheme for P₅-free graphs
- Approximate proof-labeling schemes
- Color-coding
- Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
- Complement reducible graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Deterministic subgraph detection in broadcast CONGEST
- Distributed Computing: A Locality-Sensitive Approach
- Distributed triangle detection via expander decomposition
- Even-cycle detection in the randomized and quantum CONGEST model
- Expected Length of the Longest Probe Sequence in Hash Code Searching
- Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
- scientific article; zbMATH DE number 7832756 (Why is no real title available?)
- scientific article; zbMATH DE number 7788631 (Why is no real title available?)
- Improved distributed expander decomposition and nearly optimal triangle enumeration
- Independent set in P₅-free graphs in polynomial time
- Independent set on P_k-free graphs in quasi-polynomial time
- Local Certification of Graph Decompositions and Applications to Minor-Free Classes
- On Distributed Listing of Cliques
- On the power of the congested clique model
- Optimal distributed all pairs shortest paths and applications
- Polynomial-time Algorithm for Maximum Weight Independent Set on P 6 -free Graphs
- Proof labeling schemes
- Simplified lower bounds on the multiparty communication complexity of disjointness
- Solving the \textsc{induced subgraph} problem in the randomized multiparty simultaneous messages model
- Sublinear-time distributed algorithms for detecting small cliques and even cycles
- Sublinear-time quantum computation of the diameter in CONGEST networks
- Trade-offs in distributed interactive proofs
This page was built for publication: Distributed complexity of \(P_k\)-freeness: decision and certification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7364401)
