Zobrazeno 1 - 10
of 73
pro vyhledávání: '"Babu, Jasine"'
Autor:
Ardra, P. S., Babu, Jasine, Kashyap, Kritika, Krithika, R., Pallathumadam, Sreejith K., Rajendraprasad, Deepak
Color-constrained subgraph problems are those where we are given an edge-colored (directed or undirected) graph and the task is to find a specific type of subgraph, like a spanning tree, an arborescence, a single-source shortest path tree, a perfect
Externí odkaz:
http://arxiv.org/abs/2403.06580
Eternal vertex cover problem is a variant of the classical vertex cover problem modeled as a two player attacker-defender game. Computing eternal vertex cover number of graphs is known to be NP-hard in general and the complexity status of the problem
Externí odkaz:
http://arxiv.org/abs/2201.06577
Publikováno v:
In Journal of Computer and System Sciences August 2024 143
A mixed multigraph is a multigraph which may contain both undirected and directed edges. An orientation of a mixed multigraph $G$ is an assignment of exactly one direction to each undirected edge of $G$. A mixed multigraph $G$ can be oriented to a st
Externí odkaz:
http://arxiv.org/abs/2105.02356
The eternal vertex cover problem is a dynamic variant of the classical vertex cover problem. It is NP-hard to compute the eternal vertex cover number of graphs and known algorithmic results for the problem are very few. This paper presents a linear t
Externí odkaz:
http://arxiv.org/abs/2005.08058
We show that for each non-negative integer k, every bipartite tournament either contains k arc-disjoint cycles or has a feedback arc set of size at most 7(k - 1).
Externí odkaz:
http://arxiv.org/abs/2002.06912
An orientation of an undirected graph $G$ is an assignment of exactly one direction to each edge of $G$. The oriented diameter of a graph $G$ is the smallest diameter among all the orientations of $G$. The maximum oriented diameter of a family of gra
Externí odkaz:
http://arxiv.org/abs/2001.03448
Autor:
Babu, Jasine
This thesis mainly focuses on algorithmic and combinatorial questions related to some geometric problems on graphs. In the last part of this thesis, a graph coloring problem is also discussed. Boxicity and Cubicity: These are graph parameters dealing
Externí odkaz:
http://etd.iisc.ernet.in/2005/3485
http://etd.iisc.ernet.in/abstracts/4352/G26379-Abs.pdf
http://etd.iisc.ernet.in/abstracts/4352/G26379-Abs.pdf
Autor:
Babu, Jasine, Prabhakaran, Veena
We obtain a new lower bound for the eternal vertex cover number of an arbitrary graph $G$, in terms of the cardinality of a vertex cover of minimum size in $G$ containing all its cut vertices. The consequences of the lower bound includes a quadratic
Externí odkaz:
http://arxiv.org/abs/1910.05042
We derive a local criterion for a plane near-triangulated graph to be perfect. It is shown that a plane near-triangulated graph is perfect if and only if it does not contain either a vertex, an edge or a triangle, the neighbourhood of which has an od
Externí odkaz:
http://arxiv.org/abs/1906.06200