Distributed interactive proofs for the recognition of some geometric intersection graph classes (Q2097349): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W4285107913
@@ Property / OpenAlex ID: W4285107913 / rank @@
+Normal rank
@@ Property / cites work @@
+Chaining algorithms for multiple genome comparison
+Normal rank
@@ Property / cites work @@
+The harmonious coloring problem is NP-complete for interval and permutation graphs
+Normal rank
@@ Property / cites work @@
+Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
+Normal rank
@@ Property / cites work @@
+On the Desirability of Acyclic Database Schemes
@@ Property / cites work: On the Desirability of Acyclic Database Schemes / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Classes: A Survey
@@ Property / cites work: Graph Classes: A Survey / rank @@
+Normal rank
@@ Property / cites work @@
+Approximate proof-labeling schemes
@@ Property / cites work: Approximate proof-labeling schemes / rank @@
+Normal rank
@@ Property / cites work @@
+An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
+Normal rank
@@ Property / cites work @@
+Trapezoid graphs and their coloring
@@ Property / cites work: Trapezoid graphs and their coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Q5315023
@@ Property / cites work: Q5315023 / rank @@
+Normal rank
@@ Property / cites work @@
+Compact Distributed Certification of Planar Graphs
+Normal rank
@@ Property / cites work @@
+Compact distributed certification of planar graphs
+Normal rank
@@ Property / cites work @@
+On distributed Merlin-Arthur decision protocols
@@ Property / cites work: On distributed Merlin-Arthur decision protocols / rank @@
+Normal rank
@@ Property / cites work @@
+Randomized proof-labeling schemes
@@ Property / cites work: Randomized proof-labeling schemes / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Coloring Circular Arcs and Chords
+Normal rank
@@ Property / cites work @@
+Maximum weight independent sets and cliques in intersection graphs of filaments
+Normal rank
@@ Property / cites work @@
+Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
+Normal rank
@@ Property / cites work @@
+The Knowledge Complexity of Interactive Proof Systems
+Normal rank
@@ Property / cites work @@
+Algorithmic graph theory and perfect graphs
@@ Property / cites work: Algorithmic graph theory and perfect graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3179347
@@ Property / cites work: Q3179347 / rank @@
+Normal rank
@@ Property / cites work @@
+Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
+Normal rank
@@ Property / cites work @@
+On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
+Normal rank
@@ Property / cites work @@
+A Simpler Linear-Time Recognition of Circular-Arc Graphs
+Normal rank
@@ Property / cites work @@
+Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
+Normal rank
@@ Property / cites work @@
+Q4268436
@@ Property / cites work: Q4268436 / rank @@
+Normal rank
@@ Property / cites work @@
+Interactive Distributed Proofs
@@ Property / cites work: Interactive Distributed Proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Brief Announcement
@@ Property / cites work: Brief Announcement / rank @@
+Normal rank
@@ Property / cites work @@
+Proof labeling schemes
@@ Property / cites work: Proof labeling schemes / rank @@
+Normal rank
@@ Property / cites work @@
+Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
+Normal rank
@@ Property / cites work @@
+An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
+Normal rank
@@ Property / cites work @@
+Algebraic methods for interactive proof systems
@@ Property / cites work: Algebraic methods for interactive proof systems / rank @@
+Normal rank
@@ Property / cites work @@
+On the 2-Chain Subgraph Cover and Related Problems
+Normal rank
@@ Property / cites work @@
+Linear-time recognition of circular-arc graphs
@@ Property / cites work: Linear-time recognition of circular-arc graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Topics in Intersection Graph Theory
@@ Property / cites work: Topics in Intersection Graph Theory / rank @@
+Normal rank
@@ Property / cites work @@
+Q6065460
@@ Property / cites work: Q6065460 / rank @@
+Normal rank
@@ Property / cites work @@
+The Power of Distributed Verifiers in Interactive Proofs
+Normal rank
@@ Property / cites work @@
+What Can be Computed Locally?
@@ Property / cites work: What Can be Computed Locally? / rank @@
+Normal rank
@@ Property / cites work @@
+Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
+Normal rank
@@ Property / cites work @@
+IP = PSPACE
@@ Property / cites work: IP = PSPACE / rank @@
+Normal rank
@@ Property / cites work @@
+Recognition of Circle Graphs
@@ Property / cites work: Recognition of Circle Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Fast distance multiplication of unit-Monge matrices
+Normal rank
@@ Property / cites work @@
+Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
+Normal rank
@@ Property / cites work @@
+Trade-offs in distributed interactive proofs
@@ Property / cites work: Trade-offs in distributed interactive proofs / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:2097349