Zobrazeno 1 - 10
of 40
pro vyhledávání: '"R. B. Sandeep"'
Publikováno v:
Algorithmica. 84:2842-2870
For a class $\mathcal{G}$ of graphs, the problem SUBGRAPH COMPLEMENT TO $\mathcal{G}$ asks whether one can find a subset $S$ of vertices of the input graph $G$ such that complementing the subgraph induced by $S$ in $G$ results in a graph in $\mathcal
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bf1954febbdcbe957e1f0b67c25ecd69
https://doi.org/10.1007/s00453-022-00991-3
https://doi.org/10.1007/s00453-022-00991-3
Publikováno v:
Journal of Graph Theory.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::26c64792967811fe6e3371692620e237
https://doi.org/10.1002/jgt.22953
https://doi.org/10.1002/jgt.22953
Publikováno v:
26th Annual European Symposium on Algorithms (ESA 2018)
An $H$-free editing problem asks whether we can edit at most $k$ edges to make a graph contain no induced copy of the fixed graph $H$. We obtain a polynomial kernel for this problem when $H$ is a diamond. The incompressibility dichotomy for $H$ being
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d2c4d737fc00e4b7b1ce106dd09d780f
https://doi.org/10.1007/s00453-021-00891-y
https://doi.org/10.1007/s00453-021-00891-y
Publikováno v:
LATIN 2022: Theoretical Informatics ISBN: 9783031206238
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ae31734f1b56a7092eebe16cb75babf2
https://doi.org/10.1007/978-3-031-20624-5_1
https://doi.org/10.1007/978-3-031-20624-5_1
Publikováno v:
Trends in Mathematics ISBN: 9783030838225
In this work we consider arc criticality in colourings of oriented graphs. We study deeply critical oriented graphs, those graphs for which the removal of any arc results in a decrease of the oriented chromatic number by 2. We prove the existence of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::46d7445f5ddf4f79eac46bfa5c9d057f
https://doi.org/10.1007/978-3-030-83823-2_101
https://doi.org/10.1007/978-3-030-83823-2_101
Publikováno v:
Graph-Theoretic Concepts in Computer Science ISBN: 9783030868376
WG
WG
For a class \(\mathcal {G}\) of graphs, the problem Subgraph Complement to \(\mathcal {G}\) asks whether one can find a subset S of vertices of the input graph G such that complementing the subgraph induced by S in G results in a graph in \(\mathcal
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::046df5edf9853b92c347a442a9128ed4
https://doi.org/10.1007/978-3-030-86838-3_9
https://doi.org/10.1007/978-3-030-86838-3_9
Autor:
Dániel Marx, R. B. Sandeep
Given a graph $G$ and an integer $k$, the $H$-free Edge Editing problem is to find whether there exists at most $k$ pairs of vertices in $G$ such that changing the adjacency of the pairs in $G$ results in a graph without any induced copy of $H$. The
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::782b2c6c94628c4da48153d8fb99e3f8
Publikováno v:
SIAM Journal on Discrete Mathematics. 31:542-561
For a graph $H$, the $H$-free Edge Deletion problem asks whether there exist at most $k$ edges whose deletion from the input graph $G$ results in a graph without any induced copy of $H$. $H$-free Edge Completion and $H$-free Edge Editing are defined
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a46e50cf86a974f0468524180db0bbf4
https://doi.org/10.1137/16m1055797
https://doi.org/10.1137/16m1055797
Publikováno v:
Algorithmica. 79:654-666
For a set $$\mathcal {H}$$ of graphs, the $$\mathcal {H}$$ -free Edge Deletion problem is to decide whether there exist at most k edges in the input graph, for some $$k\in \mathbb {N}$$ , whose deletion results in a graph without an induced copy of a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e94e7b957b62bc26aba77b5981290092
https://doi.org/10.1007/s00453-016-0215-y
https://doi.org/10.1007/s00453-016-0215-y
Autor:
Yixin Cao, R. B. Sandeep
Publikováno v:
Information and Computation. 271:104514
Given an $n*n$ sparse symmetric matrix with $m$ nonzero entries, performing Gaussian elimination may turn some zeroes into nonzero values. To maintain the matrix sparse, we would like to minimize the number $k$ of these changes, hence called the mini
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::550ed81e0f3f0412867e8110f0ac9ee0
https://doi.org/10.1016/j.ic.2020.104514
https://doi.org/10.1016/j.ic.2020.104514