4333882
Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
Our main result is a linear-time (that is, time $O(m+n)$) algorithm to recognize and represent proper circular-arc graphs. The best previous algorithm, due to A. Tucker, has time complexity $O(n^2)$. We take advantage of the fact that (among connected graphs) proper circular-arc graphs are precisely the graphs orientable as local tournaments, and we use a new characterization of local tournaments. The algorithm depends on repeated representation of portions of the input graph as proper interval graphs. Thus we also find it useful to give a new linear-time algorithm to represent proper interval graphs. This latter algorithm also depends on an orientation characterization of proper interval graphs. It is conceptually simple and does not use complex data structures. As a byproduct of the correctness proof of the algorithm, we also obtain a new proof of a characterization of proper interval graphs by forbidden subgraphs.
4789976
In-Tournament Digraphs
Abstract In this paper we introduce a generalization of digraphs that are locally tournaments (and hence of tournaments). This is the class of in-tournament digraphs-the set of predecessors of every vertex induces a tournament. We show that many properties of local tournament digraphs can be extended even to in-tournament digraphs. For instance, any strongly connected in-tournament digraph has a directed hamiltonian cycle. We prove that the underlying graph of any in-tournament digraph is l-homotopic. We investigate the problem of which graphs are orientable as in-tournament digraphs and prove that any graph representable as an intersection subgraph of a unicyclic graph can be so oriented. It is shown that there is a polynomial algorithm for recognizing those graphs that can be oriented as in-tournament digraphs.
14351696
A sufficient condition for a semicomplete multipartite digraph to be Hamiltonian
Abstract A multipartite tournament is an orientation of a complete k -partite graph for some k ⩾ 2. A factor of a digraph D is a collection of vertex disjoint cycles covering all the vertices of D . We show that there is no degree of strong connectivity which together with the existence of a factor will guarantee that a multipartite tournament is Hamiltonian. Our main result is a sufficient condition for a multipartite tournament to be Hamiltonian. We show that this condition is general enough to provide easy proofs of many existing results on paths and cycles in multipartite tournaments. Using this condition, we obtain a best possible lower bound on the length of a longest cycle in any strongly connected multipartite tournament.
43442956
Representation characterizations of chordal bipartite graphs
A bipartite graph is chordal bipartite if it does not contain an induced cycle of length at least six. We give three representation characterizations of chordal bipartite graphs. More precisely, we show that a bipartite graph is chordal bipartite if and only if the complement is the intersection graph of a family of pairwise compatible claws in a weighted hypercircle. (A hypercircle is a graph which consists of internally vertex disjoint paths between two distinguished vertices, and a claw in a hypercircle is a connected subgraph containing exactly one of the two distinguished vertices.) We also introduce two classes of bipartite graphs, both containing interval bigraphs and interval containment bigraphs. They are compatible subtree intersection bigraphs and compatible subtree containment bigraphs. We show that these two classes are identical to the class of chordal bipartite graphs.
10979198
Weakly Hamiltonian-connected ordinary multipartite tournaments
Abstract We characterize weakly Hamiltonian-connected ordinary multipartite tournaments. Our result generalizes such a characterization for tournaments by Thomassen and implies a polynomial algorithm to decide the existence of a Hamiltonian path connecting two given vertices in an ordinary multipartite tournament and finds one, if it exists.
31025959
A Note on Spanning Local Tournaments in Locally Semicomplete Digraphs
We prove a result which implies that every k-connected locally semicomplete digraph which is not a semicomplete digraph must contain a k-connected spanning local tournament. This improves an earlier result of Guo and partially answers a question of Jackson and Thomassen.
16721854
Learning from labeled and unlabeled data on a directed graph
We propose a general framework for learning from labeled and unlabeled data on a directed graph in which the structure of the graph including the directionality of the edges is considered. The time complexity of the algorithm derived from this framework is nearly linear due to recently developed numerical techniques. In the absence of labeled instances, this framework can be utilized as a spectral clustering method for directed graphs, which generalizes the spectral clustering approach for undirected graphs. We have applied our framework to real-world web classification problems and obtained encouraging results.
1676234
A complete distance field representation
Distance fields are an important volume representation. A high quality distance field facilitates accurate surface characterization and gradient estimation. However, due to Nyquist's law, no existing volumetric methods based on the linear sampling theory can fully capture surface details, such as comers and edges, in 3D space. We propose a novel complete distance field representation (CDFR) that does not rely on Nyquist's sampling theory. To accomplish this, we construct a volume where each voxel has a complete description of all portions of surface that affect the local distance field. For any desired distance, we are able to extract a surface contour in true Euclidean distance, at any level of accuracy, from the same CDFR representation. Such point-based iso-distance contours have faithful per-point gradients and can be interactively visualized using splatting, providing per-point shaded image quality. We also demonstrate applying CDFR to a cutting edge design for manufacturing application involving high-complexity parts at unprecedented accuracy using only commonly available computational resources.
2713872
A BIST scheme for on-chip ADC and DAC testing
In this paper we present a BIST scheme for testing on-chip A/D and D/A converters. We discuss on-chip generation of linear ramps as test stimuli, and propose techniques for measuring the DNL and INL of the converters. We validate the scheme with software simulation-5% LSB (least significant bit) test accuracy can be achieved in the presence of reasonable analog imperfection.
16485757
Reverse Engineering MAC
This paper reverse engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that the contention resolution algorithm in such protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse engineered from the protocol description, through a stochastic subgradient method in which the link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. The minimum amount of backoff aggressiveness needed for uniqueness of Nash equilibrium and convergence of the best response strategy are established as a function of user density. Convergence properties and connection with the best response strategy are also proved for variants of the stochastic-subgradient-based dynamics of the game. Together with known results in reverse engineering TCP and BGP, this paper completes the recent efforts in reverse engineering the main protocols in layers 2-4.
2569105
Implicit brushing and target snapping: data exploration and sense-making on large displays
During grouping tasks for data exploration and sense-making, the criteria are normally not well-defined. When users are bringing together data objects thought to be similar in some way, implicit brushing continually detects for groups on the freeform workspace, analyzes the groups' text content or metadata, and draws attention to related data by displaying visual hints and animation. This provides helpful tips for further grouping, group meaning refinement and structure discovery. The sense-making process is further enhanced by retrieving relevant information from a database or network during the brushing. Closely related to implicit brushing, target snapping provides a useful means to move a data object to one of its related groups on a large display. Natural dynamics and smooth animations also help to prevent distractions and allow users to concentrate on the grouping and thinking tasks. Two different prototype applications, note grouping for brainstorming and photo browsing, demonstrate the general applicability of the technique.