检索结果-内蒙古大学图书馆

The round-up property of the fractional chromatic number for proper circular arc graphs

JOURNAL OF GRAPH THEORY 2000年第4期33卷 256-267页

作者： Niessen, T Kind, J Rhein Westfal TH Aachen Inst Stat D-52056 Aachen Germany

Let G = (V, E) be a graph and let k be a nonnegative integer. A vector c is an element of Z (V)(+) is called k-colorable iff there exists a coloring of G with k colors that assigns exactly c(upsilon) colors to vertex upsilon is an element of V. Denote by (X)(G) and (Xf)(G) the chromatic number and fractional chromatic number, respectively. We prove that (X)(G) = inverted right perpendicular (Xf)(G) inverted left perpendicular holds for every proper circular are graph G. For this purpose, a more general round-up property is characterized by means of a polyhedral description of all k-colorable vectors. Both round-up properties are equivalent for proper circular are graphs. The polyhedral description is established and, as a by-product, a known coloring algorithm is generalized to multicolorings. The round-up properties do not hold for the larger classes of circular are graphs and circle graphs, unless P = NP. (C) 2000 John Wiley & Sons, Inc.

关键词： chromatic number fractional chromatic number round-up property multicoloring stable set polytope circular arc graphs

来源：评论

学校读者我要写书评

暂无评论

A constant factor approximation algorithm for boxicity of circular arc graphs

引用

DISCRETE APPLIED MATHEMATICS 2014年 178卷 1-18页

作者： Adiga, Abhijin Babu, Jasine Chandran, L. Sunil Virginia Tech Virginia Bioinformat Inst Network Dynam & Simulat Sci Lab Blacksburg VA 24061 USA Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India

The boxicity (resp. cubicity) of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (resp. cubes) in R-k. Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V, such that the intersection of their edge sets is E. The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O(n(1-epsilon))-factor for any epsilon > 0 in polynomial time, unless NP = ZPP. For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n(1-epsilon)-factor approximation algorithm for computing boxicity in polynomial time, for any epsilon > 0. In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs intersection graphs of arcs of a circle. circular arc graphs are known to have unbounded boxicity, which could be as large as Omega(n). We give a (2 + 1/k) -factor (resp. (2 + [log n]/k)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k >= 1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn + n(2)) in both these cases, and in O(mn + kn(2)) = O(n(3)) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Boxicity Cubicity circular arc graphs Approximation algorithm Normal circular arc graphs

来源：评论

学校读者我要写书评

暂无评论

Interval bigraphs and circular arc graphs

引用

JOURNAL OF GRAPH THEORY 2004年第4期46卷 313-327页

作者： Hell, P Huang, J Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Univ Victoria Dept Math & Stat Victoria BC V8W 3P4 Canada

We prove that the complements of interval bigraphs are precisely those circular arc graphs of clique covering number two, which admit a representation without two arcs covering the whole circle. We give another characterization of interval bigraphs, in terms of a vertex ordering, that we hope may prove helpful in finding a more efficient recognition algorithm than presently known. We use these results to show equality, amongst bipartite graphs, of several classes of structured graphs (proper interval bigraphs, complements of proper circular arc graphs, asteroidal-triple-free graphs, permutation graphs, and co-comparability graphs). Our results verify a conjecture of Lundgren and disprove a conjecture of Muller. (C) 2004 Wiley Periodicals, Inc.

关键词： interval graphs interval bigraphs circular arc graphs proper interval graphs proper interval bigraphs proper circular arc graphs asteroidal triples edge asteroids

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT PARALLEL RECOGNITION OF SOME circular arc graphs .1.

引用

ALGORITHMICA 1993年第3期9卷 217-238页

作者： CHEN, L 1. Department of Computer and Information Science Ohio State University 43210 Columbus OH USA

We present the first efficient parallel algorithms for recognizing some subclasses of circular arc graphs including GAMMA circular arc graphs and proper interval graphs. These algorithms run in 0(log2 n) time with 0(n3) processors on a CRCW PRAM. An intersection representation can also be constructed within the same resource bounds. Furthermore, we propose some new characterizations of THETA circular arc graphs and proper interval graphs.

关键词： circular arc graphs INTERVAL graphs CONSECUTIVE ONES PROPERTY PARALLEL ALGORITHM PRAM CLAW-FREE graphs

来源：评论

学校读者我要写书评

暂无评论

Revisiting Tucker's algorithm to color circular arc graphs

引用

SIAM JOURNAL ON COMPUTING 2003年第4期32卷 1067-1072页

作者： Valencia-Pabon, M Univ Los Andes Dept Matemat Bogota Colombia

The circular arc coloring problem consists of finding a minimum coloring of a circular arc family F such that no two intersecting arcs share a color. Let l be the minimum number of circular arcs in F that are needed to cover the circle. Tucker shows in [SIAM J. Appl. Math., 29 ( 1975), pp. 493-502], that if l greater than or equal to 4, then [3/2L] colors suffice to color F, where L denotes the load of F. We extend Tucker's result by showing that if l greater than or equal to 5, then [(l-1/l-2)L] colors suffice to color F, and this upper bound is tight.

关键词： graph algorithms chromatic number circular arc graphs induced cycles

来源：评论

学校读者我要写书评

暂无评论

A Constant Factor Approximation Algorithm for Boxicity of circular arc graphs

A Constant Factor Approximation Algorithm for Boxicity of Ci...

引用

12th International Symposium on Algorithms and Data Structures (WADS)

作者： Adiga, Abhijin Babu, Jasine Chandran, L. Sunil Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India

ISBN: (纸本)9783642222993

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional axis parallel boxes in R-k. Equivalently, it is the minimum number of interval graphs on the vertex set V such that the intersection of their edge sets is E. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below O(n(0.5-epsilon))-factor, for any epsilon > 0 in polynomial time unless NP = ZPP. Till date, there is no well known graph class of unbounded boxicity for which even an n(epsilon)-factor approximation algorithm for computing boxicity is known, for any epsilon < 1. In this paper, we study the boxicity problem on circular arc graphs intersection graphs of arcs of a circle. We give a (2+1/k)-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where k >= 1 is its boxicity. For Normal circular arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is O(mn+n(2)) in both these cases and in O(mn+kn(2)) which is at most O(n(3)) time we also get their corresponding box representations, where a is the number of vertices of the graph and m is its number of edges. The additive 2-factor algorithm directly works for any Proper circular arc graph, since computing an NCA model for it can be done in polynomial time.

关键词： Boxicity circular arc graphs Approximation Algorithm

来源：评论

学校读者我要写书评

暂无评论

Extending Partial Representations of circular-arc graphs 1

引用

48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Fiala, Jiri Rutter, Ignaz Stumpf, Peter Zeman, Peter Charles Univ Prague Dept Appl Math Prague Czech Republic Univ Passau Fac Comp Sci & Math Passau Germany Univ Neuchatel Inst Mathemat Neuchatel Switzerland

ISBN: (数字)9783031159145

ISBN: (纸本)9783031159145;9783031159138

The partial representation extension problem generalizes the recognition problem for classes of graphs defined in terms of geometric representations. We consider this problem for circular-arc graphs, where several arcs are predrawn and we ask whether this partial representation can be completed. We show that this problem is NP-complete for circular-arc graphs, answering a question of Klavik et al. (2014). We complement this hardness with tractability results of the representation extension problem for various subclasses of circular-arc graphs. We give linear-time algorithms for extending normal proper Helly and proper Helly representations. For normal Helly circular-arc representations we give an O(n(3))-time algorithm where n is the number of vertices. Surprisingly, for Helly representations, the complexity hinges on the seemingly irrelevant detail of whether the predrawn arcs have distinct or non-distinct endpoints: In the former case the algorithm for normal Helly circular-arc representations can be extended, whereas the latter case turns out to be NP-complete. We also prove that the partial representation extension problem for unit circular-arc graphs is N P-complete.

关键词： Partial representation extension circular arc graphs Helly circular arc graphs

来源：评论

学校读者我要写书评

暂无评论

On orthogonal ray graphs

引用

DISCRETE APPLIED MATHEMATICS 2010年第15期158卷 1650-1659页

作者： Shrestha, Anish Man Singh Tayu, Satoshi Ueno, Shuichi Tokyo Inst Technol Dept Commun & Integrated Syst Tokyo 1528550 Japan

An orthogonal ray graph is an intersection graph of horizontal and vertical rays (half-lines) in the xy-plane. An orthogonal ray graph is a 2-directional orthogonal ray graph if all the horizontal rays extend in the positive x-direction and all the vertical rays extend in the positive y-direction. We first show that the class of orthogonal ray graphs is a proper subset of the class of unit grid intersection graphs. We next provide several characterizations of 2-directional orthogonal ray graphs. Our first characterization is based on forbidden submatrices. A characterization in terms of a vertex ordering follows immediately. Next, we show that 2-directional orthogonal ray graphs are exactly those bipartite graphs whose complements are circular arc graphs. This characterization implies polynomial-time recognition and isomorphism algorithms for 2-directional orthogonal ray graphs. It also leads to a characterization of 2-directional orthogonal ray graphs by a list of forbidden induced subgraphs. We also show a characterization of 2-directional orthogonal ray trees, which implies a linear-time algorithm to recognize such trees. Our results settle an open question of deciding whether a (0. 1)-matrix can be permuted to avoid the submatrices (C) 2010 Elsevier B.V. All rights reserved.

关键词： Intersection graphs (Two-directional) orthogonal ray graphs circular arc graphs Bipartite posets of interval dimension two Edge-asteroids

来源：评论

学校读者我要写书评

暂无评论

On a graph-theoretical model for cyclic register allocation

引用

DISCRETE APPLIED MATHEMATICS 1999年第2-3期93卷 191-203页

作者： de Werra, D Eisenbeis, C Lelait, S Marmol, B Ecole Polytech Fed Lausanne Lausanne Switzerland INRIA Le Chesnay France Tech Univ Vienna Inst Computersprachen A-1060 Vienna Austria INRIA Rhone Alpes Montbonnot St Martin France

In the process of compiling a computer programme, we consider the problem of allocating variables to registers within a loop. It can be formulated as a coloring problem in a circular are graph (intersection graph of a family F of intervals on a circle). We consider the meeting graph of F introduced by Eisenbeis, Lelait and Marmol. Proceedings of the Fifth Workshop on Compilers for Parallel Computers, Malaga, June 1995, pp. 502-515. Characterizations of meeting graphs ale developed and their basic properties are derived with graph theoretical arguments. Furthermore some properties of the chromatic number for periodic circular are graphs are derived. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： register allocation compilation circular arc graphs coloring microprocessor design cyclic scheduling

来源：评论

学校读者我要写书评

暂无评论

List matrix partitions of graphs representing geometric configurations

引用

DISCRETE APPLIED MATHEMATICS 2019年 260卷 237-243页

作者： Valadkhan, Payam Inst Res Fundamental Sci IPM Sch Comp Sci POB 19395-5746 Tehran Iran

We introduce a certain property of graphs which allows us to develop efficient algorithms to solve a group of graph partition problems. These problems, which are formalized as M-partition problems, generalize the k-coloring and the H-coloring problems, as well as many other well-known graph problems. We show that this property holds for several graph classes representing geometric configurations, particularly such well-known classes as interval graphs, permutation graphs and circular arc graphs. (C) 2019 Elsevier B.V. All rights reserved.

关键词： List M-partition problem Graph partitions Special graph classes Interval graphs Permutation graphs circular arc graphs

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：