| |
Browse All Reviews > Mathematics Of Computing (G) > Discrete Mathematics (G.2) > Graph Theory (G.2.2) > Trees (G.2.2...)
|
|
 |
|
|
| |
|
|
| |
1-10 of 37
Reviews about "Trees (G.2.2...)":
|
Date Reviewed |
| |
Improved parameterized and exact algorithms for cut problems on trees
Kanj I., Lin G., Liu T., Tong W., Xia G., Xu J., Yang B., Zhang F., Zhang P., Zhu B. Theoretical Computer Science 607, Part 3, 455-470, 2015. Type: Article
Multicut and multiway cut problems on graphs have received significant attention in the literature. Both of the problems are hard and have interesting applications. The authors of this paper study variants of the above problems. In par...
|
Mar 8 2016 |
| |
The sandpile group of a tree
Levine L. European Journal of Combinatorics 30(4): 1026-1035, 2009. Type: Article
Consider a finite graph G with n vertices. Call the vertex xn the sink. Then, the reduced Laplacian is an (n-1) × (n-1)...
|
Aug 13 2009 |
| |
Non-cooperative tree creation
Hoefer M. Algorithmica 53(1): 104-131, 2009. Type: Article
This paper contributes to the application of game theory to network design. The objective is to investigate the extent to which useful connected subnetworks can be constructed on, say, the Internet, by selfish participants. Hoefer defi...
|
Jun 16 2009 |
| |
On the partial terminal Steiner tree problem
Hsieh S., Gao H. The Journal of Supercomputing 41(1): 41-52, 2007. Type: Article
The Steiner tree problem (STP) is among the most interesting problems in graph theory. Historically, the Steiner tree problem has attracted the attention of many researchers. Indeed, the STP is among Karp’s 21 nondeterministi...
|
Aug 26 2008 |
| |
A limit characterization for the number of spanning trees of graphs
Nikolopoulos S., Nomikos C., Rondogiannis P. Information Processing Letters 90(6): 307-313, 2004. Type: Article
This paper presents some results of an analysis of a limit characterization of the behavior of graph classes, with regard to their number of spanning trees. Let Kn-G be the graph resulting from the complete graph
|
Oct 11 2004 |
| |
Macro forest transducers
Perst T., Seidl H. Information Processing Letters 89(3): 141-149, 2004. Type: Article
The concept of macro tree transducers (MTTs) is extended to macro forest transducers (MFTs) in this paper. The new concept is derived by enhancing MTTs with concatenation. It is shown that MFTs form a strict superset of MTTs. It is als...
|
May 6 2004 |
| |
A PTAS for weight constrained Steiner trees in series-parallel graphs
Chen G., Xue G. Theoretical Computer Science 304(1-3): 237-247, 2003. Type: Article
In this paper, the authors derive a polynomial time approximation scheme (PTAS) for the weight-constrained minimum cost Steiner tree problem (WCSTP) for a special class of graphs, knows as series-parallel (S-P) graphs. An S-P graph is ...
|
Jan 6 2004 |
| |
Efficient dynamic embeddings of binary trees into hypercubes
Heun V., Mayr E. Journal of Algorithms 43(1): 51-84, 2002. Type: Article
As the title states, this paper is about embedding an arbitrary binary tree into a hypercube. This problem is important because it is a generalization of the very practical problem of matching an algorithm’s communication pat...
|
Sep 25 2003 |
| |
The Integral Tree Representation of the Symmetric Group
Whitehouse S. Journal of Algebraic Combinatorics: An International Journal 13(3): 317-326, 2001. Type: Article
This paper studies the integral representations Vn and Vn′ of the symmetric groups &Sgr;n and &Sgr;n
|
Mar 11 2003 |
| |
On the descriptive and algorithmic power of parity ordered binary decision diagrams
Waack S. Information and Computation 166(1): 61-70, 2001. Type: Article
The ordered binary decision diagram (OBDD) is a data structure used for representing Boolean functions, which are often utilized for formal circuit verification. The author analyzes what he calls the shared parity OBDD. He presents an ...
|
Jun 1 2001 |
| |
|
|
| |
|
|
