Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRecognizing (Unit) Interval Graphs by Zigzag Graph Searches
245
0
0.0
(
0
)
Added by
Yixin Cao
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Yixin Cao
Ask ChatGPT about the research
No Arabic abstract
Corneil, Olariu, and Stewart [SODA 1998; SIAM Journal on Discrete Mathematics 2009] presented a recognition algorithm for interval graphs by six graph searches. Li and Wu [Discrete Mathematics & Theoretical Computer Science 2014] simplified it to only four. The great simplicity of the latter algorithm is however eclipsed by the complicated and long proofs. The main purpose of this paper is to present a new and significantly short proof for Li and Wus algorithm, as well as a simpler implementation. We also give a self-contained simpler interpretation of the recognition algorithm of Corneil [Discrete Applied Mathematics 2004] for unit interval graphs, based on three sweeps of graph searches. Moreover, we show that two sweeps are already sufficient. Toward the proofs of the main results, we make several new structural observations that might be of independent interests.
rate research
Read More
In this paper we extend the work of Rautenbach and Szwarcfiter by giving a structural characterization of graphs that can be represented by the intersection of unit intervals that may or may not contain their endpoints. A characterization was proved independently by Joos, however our approach provides an algorithm that produces such a representation, as well as a forbidden graph characterization.
We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real line, with an edge between two vertices if and only if an interval associated to one vertex has a nonempty intersection with an interval associated to the other vertex. A graph on n vertices is a k-gap interval graph if it has a multiple interval representation with at most n+k intervals in total. In order to scale up the nice algorithmic properties of interval graphs (where k=0), we parameterize graph problems by k, and find FPT algorithms for several problems, including Feedback Vertex Set, Dominating Set, Independent Set, Clique, Clique Cover, and Multiple Interval Transversal. The Coloring problem turns out to be W[1]-hard and we design an XP algorithm for the recognition problem.
Let $G=(V,E)$ be an undirected graph. We call $D_t subseteq V$ as a total dominating set (TDS) of $G$ if each vertex $v in V$ has a dominator in $D$ other than itself. Here we consider the TDS problem in unit disk graphs, where the objective is to find a minimum cardinality total dominating set for an input graph. We prove that the TDS problem is NP-hard in unit disk graphs. Next, we propose an 8-factor approximation algorithm for the problem. The running time of the proposed approximation algorithm is $O(n log k)$, where $n$ is the number of vertices of the input graph and $k$ is output size. We also show that TDS problem admits a PTAS in unit disk graphs.
The interval graph for a set of intervals on a line consists of one vertex for each interval, and an edge for each intersecting pair of intervals. A probe interval graph is a variant that is motivated by an application to genomics, where the intervals are partitioned into two sets: probes and non-probes. The graph has an edge between two vertices if they intersect and at least one of them is a probe. We give a linear-time algorithm for determining whether a given graph and partition of vertices into probes and non-probes is a probe interval graph. If it is, we give a layout of intervals that proves this. We can also determine whether the layout of the intervals is uniquely constrained within the same time bound. As part of the algorithm, we solve the consecutive-ones probe matrix problem in linear time, develop algorithms for operating on PQ trees, and give results that relate PQ trees for different submatrices of a consecutive-ones matrix.
Greedy routing has been studied successfully on Euclidean unit disk graphs, which we interpret as a special case of hyperbolic unit disk graphs. While sparse Euclidean unit disk graphs exhibit grid-like structure, we introduce strongly hyperbolic unit disk graphs as the natural counterpart containing graphs that have hierarchical network structures. We develop and analyze a routing scheme that utilizes these hierarchies. On arbitrary graphs this scheme guarantees a worst case stretch of $max{3, 1+2b/a}$ for $a > 0$ and $b > 1$. Moreover, it stores $mathcal{O}(k(log^2{n} + log{k}))$ bits at each vertex and takes $mathcal{O}(k)$ time for a routing decision, where $k = pi e (1 + a)/(2(b - 1)) (b^2 text{diam}(G) - 1) R + log_b(text{diam}(G)) + 1$, on strongly hyperbolic unit disk graphs with threshold radius $R > 0$. In particular, for hyperbolic random graphs, which have previously been used to model hierarchical networks like the internet, $k = mathcal{O}(log^2{n})$ holds asymptotically almost surely. Thus, we obtain a worst-case stretch of $3$, $mathcal{O}(log^4 n)$ bits of storage per vertex, and $mathcal{O}(log^2 n)$ time per routing decision on such networks. This beats existing worst-case lower bounds. Our proof of concept implementation indicates that the obtained results translate well to real-world networks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
