8 Search Results for "Foucaud, Florent"

Document
DOI: 10.4230/LIPIcs.MFCS.2023.32
Isometric Path Complexity of Graphs

Authors: Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud, and Yann Vaxès

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
A set S of isometric paths of a graph G is "v-rooted", where v is a vertex of G, if v is one of the end-vertices of all the isometric paths in S. The isometric path complexity of a graph G, denoted by ipco (G), is the minimum integer k such that there exists a vertex v ∈ V(G) satisfying the following property: the vertices of any isometric path P of G can be covered by k many v-rooted isometric paths. First, we provide an O(n² m)-time algorithm to compute the isometric path complexity of a graph with n vertices and m edges. Then we show that the isometric path complexity remains bounded for graphs in three seemingly unrelated graph classes, namely, hyperbolic graphs, (theta, prism, pyramid)-free graphs, and outerstring graphs. Hyperbolic graphs are extensively studied in Metric Graph Theory. The class of (theta, prism, pyramid)-free graphs are extensively studied in Structural Graph Theory, e.g. in the context of the Strong Perfect Graph Theorem. The class of outerstring graphs is studied in Geometric Graph Theory and Computational Geometry. Our results also show that the distance functions of these (structurally) different graph classes are more similar than previously thought. There is a direct algorithmic consequence of having small isometric path complexity. Specifically, using a result of Chakraborty et al. [ISAAC 2022], we show that if the isometric path complexity of a graph G is bounded by a constant k, then there exists a k-factor approximation algorithm for Isometric Path Cover, whose objective is to cover all vertices of a graph with a minimum number of isometric paths.
Cite as

Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud, and Yann Vaxès. Isometric Path Complexity of Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.MFCS.2023.32,
  author =	{Chakraborty, Dibyayan and Chalopin, J\'{e}r\'{e}mie and Foucaud, Florent and Vax\`{e}s, Yann},
  title =	{{Isometric Path Complexity of Graphs}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.32},
  URN =		{urn:nbn:de:0030-drops-185666},
  doi =		{10.4230/LIPIcs.MFCS.2023.32},
  annote =	{Keywords: Shortest paths, Isometric path complexity, Hyperbolic graphs, Truemper Configurations, Outerstring graphs, Isometric Path Cover}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.12
Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond

Authors: Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat, and Subir Kumar Ghosh

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
A path is isometric if it is a shortest path between its endpoints. In this article, we consider the graph covering problem Isometric Path Cover, where we want to cover all the vertices of the graph using a minimum-size set of isometric paths. Although this problem has been considered from a structural point of view (in particular, regarding applications to pursuit-evasion games), it is little studied from the algorithmic perspective. We consider Isometric Path Cover on chordal graphs, and show that the problem is NP-hard for this class. On the positive side, for chordal graphs, we design a 4-approximation algorithm and an FPT algorithm for the parameter solution size. The approximation algorithm is based on a reduction to the classic path covering problem on a suitable directed acyclic graph obtained from a breadth first search traversal of the graph. The approximation ratio of our algorithm is 3 for interval graphs and 2 for proper interval graphs. Moreover, we extend the analysis of our approximation algorithm to k-chordal graphs (graphs whose induced cycles have length at most k) by showing that it has an approximation ratio of k+7 for such graphs, and to graphs of treelength at most 𝓁, where the approximation ratio is at most 6𝓁+2.
Cite as

Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat, and Subir Kumar Ghosh. Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ISAAC.2022.12,
  author =	{Chakraborty, Dibyayan and Dailly, Antoine and Das, Sandip and Foucaud, Florent and Gahlawat, Harmender and Ghosh, Subir Kumar},
  title =	{{Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.12},
  URN =		{urn:nbn:de:0030-drops-172974},
  doi =		{10.4230/LIPIcs.ISAAC.2022.12},
  annote =	{Keywords: Shortest paths, Isometric path cover, Chordal graph, Interval graph, AT-free graph, Approximation algorithm, FPT algorithm, Treewidth, Chordality, Treelength}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.40
On Graphs Coverable by k Shortest Paths

Authors: Maël Dumas, Florent Foucaud, Anthony Perez, and Ioan Todinca

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We show that if the edges or vertices of an undirected graph G can be covered by k shortest paths, then the pathwidth of G is upper-bounded by a function of k. As a corollary, we prove that the problem Isometric Path Cover with Terminals (which, given a graph G and a set of k pairs of vertices called terminals, asks whether G can be covered by k shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem Strong Geodetic Set with Terminals (which, given a graph G and a set of k terminals, asks whether there exist binom(k,2) shortest paths, each joining a distinct pair of terminals such that these paths cover G). Moreover, this implies that the related problems Isometric Path Cover and Strong Geodetic Set (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter k.
Cite as

Maël Dumas, Florent Foucaud, Anthony Perez, and Ioan Todinca. On Graphs Coverable by k Shortest Paths. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dumas_et_al:LIPIcs.ISAAC.2022.40,
  author =	{Dumas, Ma\"{e}l and Foucaud, Florent and Perez, Anthony and Todinca, Ioan},
  title =	{{On Graphs Coverable by k Shortest Paths}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{40:1--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.40},
  URN =		{urn:nbn:de:0030-drops-173251},
  doi =		{10.4230/LIPIcs.ISAAC.2022.40},
  annote =	{Keywords: Shortest paths, covering problems, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.45
On the Cop Number of String Graphs

Authors: Sandip Das and Harmender Gahlawat

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Cops and Robber is a well-studied two-player pursuit-evasion game played on a graph, where a group of cops tries to capture the robber. The cop number of a graph is the minimum number of cops required to capture the robber. We show that the cop number of a string graph is at most 13, improving upon a result of Gavenčiak et al. [Eur. J. of Comb. 72, 45-69 (2018)]. Using similar techniques, we also show that four cops have a winning strategy for a variant of Cops and Robber, named Fully Active Cops and Robber, on planar graphs, addressing an open question of Gromovikov et al. [Austr. J. Comb. 76(2), 248-265 (2020)].
Cite as

Sandip Das and Harmender Gahlawat. On the Cop Number of String Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ISAAC.2022.45,
  author =	{Das, Sandip and Gahlawat, Harmender},
  title =	{{On the Cop Number of String Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{45:1--45:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.45},
  URN =		{urn:nbn:de:0030-drops-173308},
  doi =		{10.4230/LIPIcs.ISAAC.2022.45},
  annote =	{Keywords: Cop number, string graphs, intersection graphs, planar graphs, pursuit-evasion games}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.51
Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

Authors: Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
For a graph G, a subset S ⊆ V(G) is called a resolving set if for any two vertices u,v ∈ V(G), there exists a vertex w ∈ S such that d(w,u) ≠ d(w,v). The Metric Dimension problem takes as input a graph G and a positive integer k, and asks whether there exists a resolving set of size at most k. This problem was introduced in the 1970s and is known to be NP-hard [GT 61 in Garey and Johnson’s book]. In the realm of parameterized complexity, Hartung and Nichterlein [CCC 2013] proved that the problem is W[2]-hard when parameterized by the natural parameter k. They also observed that it is FPT when parameterized by the vertex cover number and asked about its complexity under smaller parameters, in particular the feedback vertex set number. We answer this question by proving that Metric Dimension is W[1]-hard when parameterized by the feedback vertex set number. This also improves the result of Bonnet and Purohit [IPEC 2019] which states that the problem is W[1]-hard parameterized by the treewidth. Regarding the parameterization by the vertex cover number, we prove that Metric Dimension does not admit a polynomial kernel under this parameterization unless NP ⊆ coNP/poly. We observe that a similar result holds when the parameter is the distance to clique. On the positive side, we show that Metric Dimension is FPT when parameterized by either the distance to cluster or the distance to co-cluster, both of which are smaller parameters than the vertex cover number.
Cite as

Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{galby_et_al:LIPIcs.MFCS.2022.51,
  author =	{Galby, Esther and Khazaliya, Liana and Mc Inerney, Fionn and Sharma, Roohani and Tale, Prafullkumar},
  title =	{{Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.51},
  URN =		{urn:nbn:de:0030-drops-168496},
  doi =		{10.4230/LIPIcs.MFCS.2022.51},
  annote =	{Keywords: Metric Dimension, Parameterized Complexity, Feedback Vertex Set}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.7
Algorithms and Complexity for Geodetic Sets on Planar and Chordal Graphs

Authors: Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou, and Bodhayan Roy

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
We study the complexity of finding the geodetic number on subclasses of planar graphs and chordal graphs. A set S of vertices of a graph G is a geodetic set if every vertex of G lies in a shortest path between some pair of vertices of S. The Minimum Geodetic Set (MGS) problem is to find a geodetic set with minimum cardinality of a given graph. The problem is known to remain NP-hard on bipartite graphs, chordal graphs, planar graphs and subcubic graphs. We first study MGS on restricted classes of planar graphs: we design a linear-time algorithm for MGS on solid grids, improving on a 3-approximation algorithm by Chakraborty et al. (CALDAM, 2020) and show that MGS remains NP-hard even for subcubic partial grids of arbitrary girth. This unifies some results in the literature. We then turn our attention to chordal graphs, showing that MGS is fixed parameter tractable for inputs of this class when parameterized by their treewidth (which equals the clique number minus one). This implies a linear-time algorithm for k-trees, for fixed k. Then, we show that MGS is NP-hard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012). As interval graphs are very constrained, to prove the latter result we design a rather sophisticated reduction technique to work around their inherent linear structure.
Cite as

Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou, and Bodhayan Roy. Algorithms and Complexity for Geodetic Sets on Planar and Chordal Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ISAAC.2020.7,
  author =	{Chakraborty, Dibyayan and Das, Sandip and Foucaud, Florent and Gahlawat, Harmender and Lajou, Dimitri and Roy, Bodhayan},
  title =	{{Algorithms and Complexity for Geodetic Sets on Planar and Chordal Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.7},
  URN =		{urn:nbn:de:0030-drops-133516},
  doi =		{10.4230/LIPIcs.ISAAC.2020.7},
  annote =	{Keywords: Geodetic set, Planar graph, Chordal graph, Interval graph, FPT algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.24
Discriminating Codes in Geometric Setups

Authors: Sanjana Dey, Florent Foucaud, Subhas C. Nandy, and Arunabha Sen

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
We study two geometric variations of the discriminating code problem. In the discrete version, a finite set of points P and a finite set of objects S are given in ℝ^d. The objective is to choose a subset S^* ⊆ S of minimum cardinality such that the subsets S_i^* ⊆ S^* covering p_i, satisfy S_i^* ≠ ∅ for each i = 1,2,…, n, and S_i^* ≠ S_j^* for each pair (i,j), i ≠ j. In the continuous version, the solution set S^* can be chosen freely among a (potentially infinite) class of allowed geometric objects. In the 1-dimensional case (d = 1), the points are placed on some fixed-line L, and the objects in S are finite segments of L (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. This is also in contrast with most geometric covering problems, which are usually polynomial-time solvable in 1D. We then design a polynomial-time 2-approximation algorithm for the 1-dimensional discrete case. We also design a PTAS for both discrete and continuous cases when the intervals are all required to have the same length. We then study the 2-dimensional case (d = 2) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-hard, and design polynomial-time approximation algorithms with factors 4+ε and 32+ε, respectively (for every fixed ε > 0).
Cite as

Sanjana Dey, Florent Foucaud, Subhas C. Nandy, and Arunabha Sen. Discriminating Codes in Geometric Setups. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ISAAC.2020.24,
  author =	{Dey, Sanjana and Foucaud, Florent and Nandy, Subhas C. and Sen, Arunabha},
  title =	{{Discriminating Codes in Geometric Setups}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.24},
  URN =		{urn:nbn:de:0030-drops-133686},
  doi =		{10.4230/LIPIcs.ISAAC.2020.24},
  annote =	{Keywords: Discriminating code, Approximation algorithm, Segment stabbing, Geometric Hitting set}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.15
Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems

Authors: Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou, and Théo Pierron

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
We study the complexity of graph modification problems with respect to homomorphism-based colouring properties of edge-coloured graphs. A homomorphism from an edge-coloured graph G to an edge-coloured graph H is a vertex-mapping from G to H that preserves adjacencies and edge-colours. We consider the property of having a homomorphism to a fixed edge-coloured graph H, which generalises the classic vertex-colourability property. The question we are interested in is the following: given an edge-coloured graph G, can we perform k graph operations so that the resulting graph admits a homomorphism to H? The operations we consider are vertex-deletion, edge-deletion and switching (an operation that permutes the colours of the edges incident to a given vertex). Switching plays an important role in the theory of signed graphs, that are 2-edge-coloured graphs whose colours are the signs + and -. We denote the corresponding problems (parameterized by k) by Vertex Deletion-H-Colouring, Edge Deletion-H-Colouring and Switching-H-Colouring. These problems generalise the extensively studied H-Colouring problem (where one has to decide if an input graph admits a homomorphism to a fixed target H). For 2-edge-coloured H, it is known that H-Colouring already captures the complexity of all fixed-target Constraint Satisfaction Problems. Our main focus is on the case where H is an edge-coloured graph of order at most 2, a case that is already interesting since it includes standard problems such as Vertex Cover, Odd Cycle Transversal and Edge Bipartization. For such a graph H, we give a PTime/NP-complete complexity dichotomy for all three Vertex Deletion-H-Colouring, Edge Deletion-H-Colouring and Switching-H-Colouring problems. Then, we address their parameterized complexity. We show that all Vertex Deletion-H-Colouring and Edge Deletion-H-Colouring problems for such H are FPT. This is in contrast with the fact that already for some H of order 3, unless PTime = NP, none of the three considered problems is in XP, since 3-Colouring is NP-complete. We show that the situation is different for Switching-H-Colouring: there are three 2-edge-coloured graphs H of order 2 for which Switching-H-Colouring is W[1]-hard, and assuming the ETH, admits no algorithm in time f(k)n^{o(k)} for inputs of size n and for any computable function f. For the other cases, Switching-H-Colouring is FPT.
Cite as

Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou, and Théo Pierron. Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{foucaud_et_al:LIPIcs.IPEC.2019.15,
  author =	{Foucaud, Florent and Hocquard, Herv\'{e} and Lajou, Dimitri and Mitsou, Valia and Pierron, Th\'{e}o},
  title =	{{Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.15},
  URN =		{urn:nbn:de:0030-drops-114765},
  doi =		{10.4230/LIPIcs.IPEC.2019.15},
  annote =	{Keywords: Graph homomorphism, Graph modification, Edge-coloured graph, Signed graph}
}
  • Refine by Author
  • 6 Foucaud, Florent
  • 3 Chakraborty, Dibyayan
  • 3 Das, Sandip
  • 3 Gahlawat, Harmender
  • 2 Lajou, Dimitri
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 3 Shortest paths
  • 2 Approximation algorithm
  • 2 Chordal graph
  • 2 FPT algorithm
  • 2 Interval graph
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 4 2022
  • 2 2020
  • 1 2019
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact