Distributed interactive proofs for the recognition of some geometric intersection graph classes
type: Item
instance of: scholarly article
title: Distributed interactive proofs for the recognition of some geometric intersection graph classes
DOI: 10.1007/978-3-031-09993-9_12
author: Benjamin Jauregui
author: Pedro Montealegre
author: Ivan Rapaport
publication date: 2022-11-11T00:00:00Z
full work available at URL: https://arxiv.org/abs/2112.03206
Mathematics Subject Classification ID: 68Mxx
Mathematics Subject Classification ID: 68Q11
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7615859
zbMATH Keywords: distributed decision
zbMATH Keywords: proof-labeling scheme
zbMATH Keywords: distributed interactive proofs
zbMATH Keywords: intersection graph classes
MaRDI profile type: Publication
OpenAlex ID: W4285107913
cites work: Chaining algorithms for multiple genome comparison
cites work: The harmonious coloring problem is NP-complete for interval and permutation graphs
cites work: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
cites work: On the Desirability of Acyclic Database Schemes
cites work: Graph Classes: A Survey
cites work: Approximate proof-labeling schemes
cites work: An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
cites work: Trapezoid graphs and their coloring
cites work: Q5315023
cites work: Compact Distributed Certification of Planar Graphs
cites work: Compact distributed certification of planar graphs
cites work: On distributed Merlin-Arthur decision protocols
cites work: Randomized proof-labeling schemes
cites work: The Complexity of Coloring Circular Arcs and Chords
cites work: Maximum weight independent sets and cliques in intersection graphs of filaments
cites work: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
cites work: The Knowledge Complexity of Interactive Proof Systems
cites work: Algorithmic graph theory and perfect graphs
cites work: Q3179347
cites work: Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
cites work: On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
cites work: A Simpler Linear-Time Recognition of Circular-Arc Graphs
cites work: Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
cites work: Q4268436
cites work: Interactive Distributed Proofs
cites work: Brief Announcement
cites work: Proof labeling schemes
cites work: Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
cites work: An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
cites work: Algebraic methods for interactive proof systems
cites work: On the 2-Chain Subgraph Cover and Related Problems
cites work: Linear-time recognition of circular-arc graphs
cites work: Topics in Intersection Graph Theory
cites work: Q6065460
cites work: The Power of Distributed Verifiers in Interactive Proofs
cites work: What Can be Computed Locally?
cites work: Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
cites work: IP = PSPACE
cites work: Recognition of Circle Graphs
cites work: Fast distance multiplication of unit-Monge matrices
cites work: Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
cites work: Trade-offs in distributed interactive proofs
description: scientific article; zbMATH DE number 7615859