The structure and number of global roundings of a graph
type: Item
instance of: scholarly article
title: The structure and number of global roundings of a graph
zbMATH Open document ID: 1057.05060
author: Tetsuo Asano
author: Hisao Tamaki
author: Takeshi Tokuyama
author: Naoki Katoh
published in: Theoretical Computer Science
publication date: 2004-10-27T00:00:00Z
review text: Let \(P= (U;E)\) be a connected labelled graph. This article considers the hypergraph \(H_G= (V,{\mathcal P}_G)\), where \(V\) is the set of vertices of \(P\). From this constructions and after the definition of discrepancy, the article deals with the maximum number of integral points in an open unit ball, using the discrepancy distance. The authors introduce some conjectures on this number, and they give some graphs for which these conjectures hold.
reviewed by: Alain Bretto
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C90
zbMATH DE Number: 2110951
zbMATH Keywords: Combinatorics
zbMATH Keywords: Rounding
zbMATH Keywords: Discrepancy
zbMATH Keywords: Graph
zbMATH Keywords: Hypergraph
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.02.044
OpenAlex ID: W1543818728
cites work: Q4829028
cites work: Optimal roundings of sequences and matrices
cites work: Q4474128
cites work: Q4871774
cites work: Q4398864
cites work: Q4515159
cites work: Lattice approximation and linear discrepancy of totally unimodular matrices. Extended abstract
cites work: Q3236252
cites work: Semi-balanced colorings of graphs: Generalized 2-colorings based on a relaxed discrepancy condition
cites work: Tight upper bounds for the discrepancy of half-spaces
cites work: Q4003879
cites work: Q4339095
cites work: Q4535017
cites work: Algorithms and Computation
DOI: 10.1016/J.TCS.2004.02.044
description: scientific article; zbMATH DE number 2110951