Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
From MaRDI portal
Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
Recommendations
- A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
- Compact distributed certification of planar graphs
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- Efficient parallel recognition of cographs
- A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
Cites work
- scientific article; zbMATH DE number 4213472 (Why is no real title available?)
- scientific article; zbMATH DE number 7765409 (Why is no real title available?)
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
- Algorithmic graph theory and perfect graphs
- Approximate proof-labeling schemes
- Brief announcement: Distributed minimum vertex coloring and maximum independent set in chordal graphs
- Compact distributed certification of planar graphs
- Compact-port routing models and applications to distance-hereditary graphs
- Complement reducible graphs
- Dacey Graphs
- Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
- Distributed algorithms for coloring interval graphs
- Distributed algorithms for planar networks. I: Planar embedding
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- Geometric algorithms and combinatorial optimization.
- Graph Classes: A Survey
- Graph reconstruction in the congested clique
- Interactive distributed proofs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- Locally checkable proofs in distributed computing
- Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets
- On a class of posets and the corresponding comparability graphs
- On a property of the class of n-colorable graphs
- On distributed Merlin-Arthur decision protocols
- Parallel Algorithm for Cograph Recognition with Applications
- Parallel recognition of complement reducible graphs and cotree construction
- Proof labeling schemes
- Randomized proof-labeling schemes
- Randomized proof-labeling schemes
- Solving the \textsc{induced subgraph} problem in the randomized multiparty simultaneous messages model
- The power of distributed verifiers in interactive proofs
- Towards a complexity theory for local distributed computing
- Trade-offs in distributed interactive proofs
- What Can be Computed Locally?
Cited in
(2)
This page was built for publication: Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6488452)
