On Properties of a Set of Global Roundings Associated with Clique Connection of Graphs
スポンサーリンク
概要
- 論文の詳細を見る
Given a connected weighted graph G=(V,E), we consider a hypergraph H(G)=(V,F(G)) corresponding to the set of all shortest paths in G. For a given real assignment a on V satisfying 0≤a(v)≤1, a global rounding α with respect to H(G) is a binary assignment satisfying that |∑v∈Fa(v)−α(v)|<1 for every F∈F(G). Asano et al. [3] conjectured that there are at most |V|+1 global roundings for H(G). In this paper, we present monotone properties on size and affine corank of a set of global roundings under a clique connection operation.
- 東北大学の論文
著者
-
Ishikawa Tomonori
Graduate School Of Information Sciences Tohoku University
-
Tokuyama Takeshi
Graduate School Of Information Science Tohoku University
-
Kawarabayashi Ken-ichi
Graduate School Of Information Sciences (gsis) Tohoku University
-
Kawarabayashi Ken-ichi
Graduate School Of Information Sciences Tohoku University
-
Kawarabayashi Ken-ich
Graduate School of Information Sciences, Tohoku University
関連論文
- Distance Trisector of a Segment and a Point
- Voronoi Diagrams with Respect to Criteria on Vision Information
- Quasi-Norms for a Double Sequence
- On Detecting Digital Line Components in a Binary Image
- Reconstructing sets from distances given by graphs (コンピュテーション)
- Discrepancy-Based Digital Halftoning: Automatic Evaluation and Optimization
- Quantum Algorithms for Intersection and Proximity Problems
- Quantum Computation in Computational Geometry
- Algorithm Aspect of Graph Minor Theory
- Algorithm Aspect of Graph Minor Theory
- Combinatorics on Arrangements and Parametric Matroids : A Bridge between Computational Geometry and Combinatorial Optimization(Special Issue on Algorithm Engineering : Surveys)
- On Properties of a Set of Global Roundings Associated with Clique Connection of Graphs
- Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication
- DS-1-11 An Algorithm for Optimally Locating Baselines using Quad Decomposition