Zero knowledge and the chromatic number

DOI10.1006/jcss.1998.1587zbMath0921.68089OpenAlexW2058422149MaRDI QIDQ1276168

Publication date: 6 October 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/40265ae8a3e103dba2f471d9bc7dde377856fe5f

zbMATH Keywords

chromatic number zero-knowledge

Mathematics Subject Classification ID

Related Items

Towards optimal lower bounds for clique and chromatic number., Coloring Jacobians revisited: a new algorithm for star and~acyclic bicoloring, Detecting almost symmetries of graphs, A fast network-decomposition algorithm and its applications to constant-time distributed computation, Direct routing: Algorithms and complexity, Scheduling with conflicts: Online and offline algorithms, Distributed computing with advice: information sensitivity of graph coloring, Blocker size via matching minors, An improved algorithm for approximating the chromatic number of \(G_{n,p}\), Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation, Coloring immersion-free graphs, On the Complexity of the Minimum Independent Set Partition Problem, On the intractability landscape of digraph intersection representations, Injective coloring of some subclasses of bipartite graphs and chordal graphs, On the complexity of deriving position specific score matrices from positive and negative sequences, Some recent progress and applications in graph minor theory, Complexity of Coloring Random Graphs, Network design under general wireless interference, Bisecting and \(D\)-secting families for set systems, On the complexity of injective colorings and its generalizations, A supernodal formulation of vertex colouring with applications in course timetabling, Average-case complexity of backtrack search for coloring sparse random graphs, Computing the partition function for graph homomorphisms with multiplicities, A pure labeled transition semantics for the applied pi calculus, The Hardness of Approximating Poset Dimension, Malleable scheduling beyond identical machines, Parameterized (Approximate) Defective Coloring, Injective colorings with arithmetic constraints, Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs, Approximate strong separation with application in fractional graph coloring and preemptive scheduling., Multicoloring trees., Unnamed Item, Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs, A competitive analysis for balanced transactional memory workloads, Approximation algorithms via contraction decomposition, Radio aggregation scheduling, Hypercontractivity via tensor calculus, A Characterization of hard-to-cover CSPs, Finer Tight Bounds for Coloring on Clique-Width, Randomly colouring graphs (a combinatorial view), A survey on the structure of approximation classes, Non-clairvoyant scheduling with conflicts for unit-size jobs, Tight results on minimum entropy set cover, On percolation and ‐hardness, Inapproximability and approximability of minimal tree routing and coloring, Polynomial cases for the vertex coloring problem, Cross-layer optimization in ultra wideband networks, Inapproximability results for combinatorial auctions with submodular utility functions, Clique Clustering Yields a PTAS for max-Coloring Interval Graphs, Computing the partition function for graph homomorphisms, On the complexity of bandwidth allocation in radio networks, On the Lovász theta function and some variants, New potential functions for greedy independence and coloring, Fractionally total colouring \(G_{n,p}\), Why almost all \(k\)-colorable graphs are easy to color, Tight approximability results for test set problems in bioinformatics, A simple algorithm for 4-coloring 3-colorable planar graphs, On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem, Semi-Definite positive Programming Relaxations for Graph K_n-Coloring in Frequency Assignment, On the tractability of coloring semirandom graphs, Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring, Conversion of coloring algorithms into maximum weight independent set algorithms, New tools and connections for exponential-time approximation, Exponential-time approximation of weighted set cover, Unnamed Item, Clique clustering yields a PTAS for max-coloring interval graphs, Fractional path coloring in bounded degree trees with applications, On the recursive largest first algorithm for graph colouring, Convex Relaxations and Integrality Gaps, On Injective Colourings of Chordal Graphs, “Rent-or-Buy” Scheduling and Cost Coloring Problems, Algorithmic and hardness results for the colorful components problems, Minimum entropy coloring, On approximating four covering and packing problems, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, Hardness of approximate two-level logic minimization and PAC learning with membership queries, A note on coloring sparse random graphs, Approximation algorithms in combinatorial scientific computing, On sum coloring and sum multi-coloring for restricted families of graphs, Conjunctive query containment revisited, Priority algorithms for graph optimization problems, Radiocoloring in planar graphs: Complexity and approximations, Effective Wireless Scheduling via Hypergraph Sketches, Unnamed Item, Minimizing maximum fiber requirement in optical networks, Heuristics for semirandom graph problems

Cites Work