Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Browse by topic Browse by titles Authors Reviewers Browse by issue Browse Help
  Browse All Reviews > Mathematics Of Computing (G) > Discrete Mathematics (G.2) > Graph Theory (G.2.2) > Graph Labeling (G.2.2...)  
  1-10 of 16 Reviews about "Graph Labeling (G.2.2...)": Date Reviewed
   An asymptotic version of the multigraph 1-factorization conjecture
Vaughan E.  Journal of Graph Theory 72(1): 19-29, 2013. Type: Article

A multigraph is a graph in which two vertices are contained in more than one edge, but loops are not allowed. A set of edges is parallel if all of its edges contain the same two vertices. The size of the largest parallel set of edges is called the...

Mar 29 2013
  Sparsity: graphs, structures, and algorithms
Nešetřil J., de Mendez P.,  Springer Publishing Company, Incorporated, New York, NY, 2012. 480 pp. Type: Book (978-3-642278-74-7)

Professors and doctoral students working in the algorithms and graphs area will appreciate this book. Researchers involved in graph structures for computer science and related fields will benefit from the in-depth overview of the book, ranging fro...

Oct 16 2012
  Sphere and dot product representations of graphs
Kang R., Müller T.  SoCG 2011 (Proceedings of the 27th Annual ACM Symposium on Computational Geometry, Paris, France,  Jun 13-15, 2011) 308-314, 2011. Type: Proceedings

Kang and M¿ller, in this paper, prove two important positive results, and one partially negative result, on graph representation. A graph G=(V,E) consists of a set of vertices V
Sep 27 2011
  Randomly coloring random graphs
Dyer M., Frieze A.  Random Structures & Algorithms 36(3): 251-272, 2010. Type: Article

The problem of coloring random graphs is a well-known problem in computer science that has received ample attention. The problem consists of finding an assignment of colors--from a predefined set--for all vertices of a graph, such that n...

Jul 8 2010
  Hadwiger’s conjecture for proper circular arc graphs
Belkale N., Chandran L.  European Journal of Combinatorics 30(4): 946-956, 2009. Type: Article

The arcs of a circle represent the vertex sets of circular graphs: “Two vertices are adjacent if and only if their corresponding arcs intersect.” A circular graph is proper if no arc representing a vertex is contained properly in anoth...

Sep 28 2009
  Hybrid object labelling in digital images
Martín-Herrero J.  Machine Vision and Applications 18(1): 1-15, 2007. Type: Article

Labelling is a computer-vision task that identifies all the connected pixels of an object with the same label. It is often followed by the feature extraction, characterization, for the further classification of objects....

Dec 21 2007
  Equitable colorings of bounded treewidth graphs
Bodlaender H., Fomin F.  Theoretical Computer Science 349(1): 22-30, 2005. Type: Article

Bodlaender and Fomin prove that an equitable k-coloring can be found in polynomial time on graphs of bounded treewidth. It follows that an l-bounded k-coloring also has a polynomial solution on graphs of bounded treewidth....

Jul 10 2006
  A linear time algorithm for the minimum weighted feedback vertex set on diamonds
Carrabs F., Cerulli R., Gentili M., Parlato G.  Information Processing Letters 94(1): 29-35, 2005. Type: Article

A linear time solution of the weighted feedback vertex problem for diamond graphs is the main contribution of this paper. The result can be obtained from a more general result [1]. There, it is shown that the regarded problem is a linear extended ...

Jan 12 2006
  3-coloring in time O(1.3289)
Beigel R., Eppstein D.  Journal of Algorithms 54(2): 168-204, 2005. Type: Article

The main result of this paper is a proof that the three-coloring problem can be solved in worst-case time O(1.3289n). The previous record for this problem was the O(1.415
Jul 5 2005
  Distance labeling in graphs
Gavoille C., Peleg D., Pérennes S., Raz R.  Journal of Algorithms 53(1): 85-112, 2004. Type: Article

This paper mainly addresses the problem of efficiently labeling graphs in such a way that the distance between two nodes of the graph can be computed only from their labels. Of course, it is desirable to have the maximum length of a label be ̶...

Jan 26 2005
Display per page
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2022 ThinkLoud, Inc.
Terms of Use
| Privacy Policy