Let t be a positive real number. A graph is called t-tough if the removal of any vertex set S that disconnects the graph leaves at most |S|/t components. The toughness of a graph is the largest t for ...which the graph is t-tough. A graph is minimally t-tough if the toughness of the graph is t and the deletion of any edge from the graph decreases the toughness. A graph is chordal if it does not contain an induced cycle of length at least 4. We characterize the minimally t-tough chordal graphs for all t≤1/2. As a corollary, a characterization of minimally t-tough interval graphs is obtained for t≤1/2.
For a graph G=(V,E) and a subset S⊆V of vertices, a vertex is happy if all its neighbor vertices in G are contained in S. Given a connected undirected graph and an integer k, the Maximum Happy Set ...Problem (MaxHS) asks to find a set S of k vertices which maximizes the number of happy vertices in S (note that all happy vertices in V belong to S). We proposed an algorithm for MaxHS on proper interval graphs in Theor. Comput. Sci. 866 (2021) 123–144. However, due to a wrong observation made by the authors, it works only on proper interval graphs obeying the observation. In this corrigendum, we propose a new algorithm which runs in O(k|V|logk+|E|) time for proper interval graphs.
A digraph G = (V, E) is an interval catch digraph if for each vertex v ∈ V , one can associate an interval on real line and a point within it (say (Iv, pv) ) in such a way that uv ∈ E if and ...only if pv ∈ Iu . It was introduced by Maehara in 1984. It has many applications in real world situations like networking and telecommunication. In his introducing paper Maehara proposed a conjecture for the characterization of central interval catch digraph (where pv is the mid-point Iv for each v ∈ V ) in terms of forbidden subdigraphs. In this paper, we disprove the conjecture by showing counter examples. Also we characterize this digraph by defining a suitable mapping from the vertex set to the real line. We study oriented interval catch digraphs and characterize an interval catch digraph when it is a tournament. Finally, we characterize a proper interval catch digraph and establish relationships between these digraph classes.
Distance queries over dynamic interval graphs Chen, Jingbang; He, Meng; Munro, J. Ian ...
Computational geometry : theory and applications,
October 2024, 2024-10-00, Letnik:
122
Journal Article
Recenzirano
Odprti dostop
We design the first dynamic distance oracles for interval graphs, which are intersection graphs of a set of intervals on the real line, and for proper interval graphs, which are intersection graphs ...of a set of intervals in which no interval is properly contained in another.
For proper interval graphs, we design a linear space data structure which supports distance queries (computing the distance between two query vertices) and vertex insertion or deletion in O(lgn) worst-case time, where n is the number of vertices currently in G. Under incremental (insertion only) or decremental (deletion only) settings in general interval graphs, we design linear space data structures that support distance queries in O(lgn) worst-case time and vertex insertion or deletion in O(lgn) amortized time, where n is the maximum number of vertices in the graph. Under fully dynamic settings in general interval graphs, we design a data structure that represents an interval graph G in O(n) words of space to support distance queries in O(nlgn/S(n)) worst-case time and vertex insertion or deletion in O(S(n)+lgn) worst-case time, where n is the number of vertices currently in G and S(n) is an arbitrary function that satisfies S(n)=Ω(1) and S(n)=O(n). This implies an O(n)-word solution with O(nlgn)-time support for both distance queries and updates. All four data structures can answer shortest path queries by reporting the vertices in the shortest path between two query vertices in O(lgn) worst-case time per vertex.
We also study the hardness of supporting distance queries under updates over an intersection graph of 3D axis-aligned line segments, which generalizes our problem to 3D. Finally, we solve the problem of computing the diameter of a dynamic connected interval graph.
•Fully dynamic proper interval graph with O(logn) time operations.•Incremental and decremental interval graph with O(logn) amortized time operations.•Fully dynamic interval graph with O(nlogn) time operations.
•A new fast optimal split for the team orienteering problem.•An effective particle swarm algorithm (PSOiA).•PSOiA is robust and outperforms the state-of-the-art algorithms in the literature.
The Team ...Orienteering Problem (TOP) is a particular vehicle routing problem in which the aim is to maximize the profit gained from visiting customers without exceeding a travel cost/time limit. This paper proposes a new and fast evaluation process for TOP based on an interval graph model and a Particle Swarm Optimization inspired Algorithm (PSOiA) to solve the problem. Experiments conducted on the standard benchmark of TOP clearly show that our algorithm outperforms the existing solving methods. PSOiA reached a relative error of 0.0005% whereas the best known relative error in the literature is 0.0394%. Our algorithm detects all but one of the best known solutions. Moreover, a strict improvement was found for one instance of the benchmark and a new set of larger instances was introduced.
A subset S of vertices of G is a total dominating set if, for any vertex v, there is a vertex in S adjacent to v. A total dominating set S is a secure total dominating set if, for any vertex v∉S, ...there is a vertex u∈S such that uv is an edge and (S∖{u})∪{v} is also a total dominating set. In this paper, we design an O(m)-time algorithm for computing a minimum secure total dominating set in a proper interval graph, where m is the number of edges.
The triangle packing problem (TPP) is to find the maximum number of pairwise vertex disjoint triangles in a given graph. The TPP is NP-complete in a general graph and even so when a given graph is ...restricted to a chordal graph. On the other hand, the TPP can be solved in polynomial time for unit interval graphs. For this reason, it is a well-known open problem to prove whether there exists a polynomial time algorithm solving the TPP on interval graphs. In this paper, we give an answer to the problem.
labeling of interval graphs Sk. Amanathulla; Biswajit Bera; Madhumangal Pal
International journal of mathematics for industry (Online),
12/2022, Letnik:
14, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Formula: see text-labeling problem (Formula: see text-Formula: see text) is an important topic in discrete mathematics due to its various applications, like in frequency assignment in mobile ...communication systems, signal processing, circuit design, etc. Formula: see text-Formula: see text is a special case of Formula: see text-Formula: see text. An Formula: see text-labeling (Formula: see text) of a graph Formula: see text is a mapping Formula: see text such that Formula: see text if and only if Formula: see text, Formula: see text if Formula: see text or 3, where Formula: see text is the distance between the nodes Formula: see text and Formula: see text. In this work, we have determined the upper bound of Formula: see text for interval graph (IG) and obtained a tighter upper bound which is Formula: see text. Also, we proposed an efficient algorithm to label any IG by Formula: see text and also computed the time complexity of the proposed algorithm.
The k-defensive domination problem, a variant of the classical domination problem on graphs, seeks a minimum cardinality vertex set providing a surjective defense against any attack on vertices of ...cardinality bounded by a parameter k, where every vertex under attack is defended by a distinct defender (which can be itself). The problem has been shown to be NP-complete for fixed k; if k is part of the input, the problem is unlikely to be in co-NP. We present efficient algorithms solving this problem on proper interval graphs with k part of the input. The algorithms use a greedy approach that takes advantage of the linear ordering of the endpoints of the intervals associated with the vertices. The first algorithm is based on the interval model and has complexity O(n⋅k) for a graph on n vertices and an attack on at most k vertices. The second one is an improvement of the first and employs bubble representations of proper interval graph to realize an improved complexity of O(n+B⋅logk) for a graph represented by B bubbles.
For efficient design of parallel algorithms on multiprocessor architectures with memory banks, simultaneous access to a specified subgraph of a graph data structure by multiple processors requires ...that the data items belonging to the subgraph reside in distinct memory banks. Such “conflict-free” access to parallel memory systems and other applied problems motivate the study of rainbow coloring of a graph, in which there is a fixed template T (or a family of templates), and one seeks to color the vertices of an input graph G with as few colors as possible, so that each copy of T in G is rainbow colored, i.e., has no two vertices the same color. In the above example, the data structure is modeled as the host graph G, and the specified subgraph as the template T. We call such coloring a template-driven rainbow coloring (or TR-coloring). For large data sets, it is also important to ensure that no memory bank (color) is overloaded, i.e., the coloring is as balanced as possible. Additionally, for fast access to data, it is desirable to quickly determine the address of a memory bank storing a data item. For arbitrary topology of G and T, finding an optimal and balanced TR-coloring is a challenging problem. This paper focuses on rainbow coloring of proper interval graphs (as hosts) for cycle templates. In particular, we present an O(k⋅|V|+|E|) time algorithm to find a TR-coloring of a proper interval graph G with respect to k-length cycle template, Ck. Our algorithm produces a coloring that is (i) optimal, i.e., it uses minimum possible number of colors in any TR-coloring; (ii) balanced, i.e, the vertices are evenly distributed among the different color classes; and (iii) explicit, i.e., the color assigned to a vertex can be computed by a closed form formula in constant time.
PDF
