28886116
A Linear-Time Algorithm for 7-Coloring 1-Plane Graphs
AbstractA graph G is 1-planar if it can be embedded in the plane in such a way 
that each edge crosses at most one other edge. Borodin showed that 
1-planar graphs are 6-colorable, but his proof does not lead to a linear-time 
algorithm. This paper presents a linear-time algorithm for 7-coloring 
1-plane graphs (which are 1-planar graphs already embedded in the plane). 
The main difficulty in the design of our algorithm comes from 
the fact that the class of 1-planar graphs is not closed under the 
operation of edge contraction. This difficulty is overcome by a structural 
lemma that may be useful in other problems on 1-planar graphs. This paper 
also shows that it is NP-complete to decide whether a given 1-planar graph 
is 4-colorable. The complexity of the problem of deciding whether a given 
1-planar graph is 5-colorable is still unknown.
32847785
Approximation Algorithms for Independent Sets in Map Graphs
This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1+? can be achieved by a quadratic-time algorithm for any given constant ??0, no matter whether each vertex of G is given a weight or not. In case G is given without a map, a ratio of 4 can be achieved by a low-degree polynomial-time algorithm if no vertex is given a weight, while a ratio of 5 can be achieved by a low-degree polynomial-time algorithm otherwise.
701
Common-Face Embeddings of Planar Graphs
Given a planar graph $\Ggg$ and a sequence ${\CC}_1,\ldots,{\CC}_q$, where each ${\CC}_i$ is a family of vertex subsets of $\Ggg$, we wish to find a plane embedding of $\Ggg$, if any exists, such that, for each $i\in\{1,\ldots,q\}$, there is a face Fi in the embedding whose boundary contains at least one vertex from each set in CCi. This problem has applications in the recovery of topological information from geographical data and the design of constrained layouts in VLSI. Let $\inputsize$ be the input size, i.e., the total number of vertices and edges in $\Ggg$ and the families CCi, counting multiplicity. We show that this problem is NP-complete in general. We also show that it is solvable in $O(\inputsize\log \inputsize)$ time for the special case in which, for each input family CCi, each set in CCi induces a connected subgraph of the input graph $\Ggg$. Note that the classical problem of simply finding a planar embedding is a further special case of this case with q=0. Therefore, the processing of the additional constraints CC1, . . .,CCq incurs only a logarithmic factor of overhead.
38006851
Approximation Algorithms for Independent Sets in Map Graphs
This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1+δ can be achieved in O(n2) time for any given constant δ > 0, no matter whether each vertex of G is given a weight or not. In case G is given without a map, a ratio of 4 can be achieved in O(n7) time if no vertex is given a weight, while a ratio of O(log n) can be achieved in O(n7 log n) time otherwise. Behind the design of our algorithms are several fundamental results for map graphs; these results can be used to design good approximation algorithms for coloring and vertex cover in map graphs, and may find applications to other problems on map graphs as well.
46287200
A Parallel Algorithm for Finding a Triconnected Component Separator with an Application
20004613
Disk Embeddings of Planar Graphs
Abstract 
Given a planar graph $G=(V,E)$ and a rooted forest ${\FF}=(V_{\FF}, A_{\FF})$ 
with leaf set $V$, we wish to decide whether $G$ has a plane embedding $\GG$ 
satisfying the following condition: There are $|V_{\FF}|-|V|$ pairwise noncrossing 
Jordan curves in the plane one-to-one corresponding to the nonleaf vertices of 
${\FF}$ such that for every nonleaf vertex $f$ of ${\FF}$, the interior of the curve 
$\JJ_f$ corresponding to $f$ contains all the leaf descendants of $f$ in ${\FF}$
but contains no other leaves of ${\FF}$. 
This problem arises from theoretical studies in geographic database systems. 
It is unknown whether this problem can be solved in polynomial time. 
This paper presents an almost linear-time algorithm for a nontrivial special case 
where the set of leaf descendants of each nonleaf vertex $f$ in ${\FF}$ induces 
a connected subgraph of $G$. 


2205670
Multiplicative Adaptive Algorithms for User Preference Retrieval
In contrast to the adoption of linear additive query updating techniques in existing popular algorithms for user preference retrieval, in this paper we design two types of algorithms, the multiplicative adaptive query expansion algorithm MA and the multiplicative adaptive gradient search algorithm MG, both of which use multiplicative query expansion strategies to adaptively improve the query vector. We prove that algorithm MA has a substantially better mistake bound than the Rocchio's and the Perceptron algorithms in learning a user preference relation determined by a linear classifier with a small number of non-zero coefficients over the real-valued vector space [0, 1]n.We also show that algorithm MG boosts the usefulness of an index term exponentially, while the gradient descent procedure does so linearly. Our work also generalize the algorithm Winnow in the following aspects: various updating functions may be used; multiplicative updating for a weight is dependent on the value of the corresponding index term, which is more realistic and applicable to real-valued vector space; and finally, a number of documents which may or may not be counterexamples to the algorithm's current classification are allowed. Practical implementations of algorithms MA and MG have been underway in the next stage development of our intelligent web search tools.
1865477
On integral sum graphs
A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v)=f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K"3 has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous related results are also presented.
35937629
Optimal Algorithms for Finding User Access Sessions from Very Large Web Logs
Although efficient identification of user access sessions from very large web logs is an unavoidable data preparation task for the success of higher level web log mining, little attention has been paid to algorithmic study of this problem. In this paper we consider two types of user access sessions, interval sessions and gap sessions. We design two efficient algorithms for finding respectively those two types of sessions with the help of new data structures. We present both theoretical and empirical analysis of the algorithms and prove that both algorithms have optimal time complexity.
207130305
On k-pairable graphs
Motivated by a 1994 result of Graham et al. (Amer. Math. Monthly 101(7) (1994) 664) about spanning trees of the graphs with an antipodal isomorphism, we introduce the concept of k-pairable graphs and extend the result in Graham et al. (Amer. Math. Monthly 101(7) (1994) 664) to this larger class of graphs. We then define a new graph parameter p(G), called the pair length of graph G. This parameter measures the maximum distance, in some sense, between a subgraph induced by half the vertices of G with the isomorphic subgraph induced by the other half of V(G). An upper bound for the parameter p(G) is given. Some properties of the k-pairable graphs and their product graphs are studied. We also post some problems for further research.
62617805
Improved rate control for MPEG-4 video transport over wireless channel
Video streaming over wireless channel is challenging due to a number of factors such as limited bandwidth and loss sensitivity. In this paper, we develop a novel rate control algorithm for MPEG-4 video coding. Unlike traditional rate control schemes, we jointly consider the encoding complexity variation and buffer variation as well as human visual properties to optimize the rate control efficiency. We also analyze the sensitivity of a macroblock (MB) as a result of bit errors and calculate its error sensitivity metric. This metric is used in unequal error protection (UEP) of the MB. Simulation results show that proposed approach can improve the decoded picture quality in wireless video coding and transmission.