8 Search Results for "Axiotis, Kyriakos"

Document
DOI: 10.4230/LIPIcs.WADS.2025.30
Convolution and Knapsack in Higher Dimensions

Authors: Kilian Grage, Klaus Jansen, and Björn Schumacher

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
In the Knapsack problem, one is given the task of packing a knapsack of a given size with items in order to gain a packing with a high profit value. As one of the most classical problems in computer science, research for this problem has gone a long way. One important connection to the (max,+)-convolution problem has been established, where knapsack solutions can be combined by building the convolution of two sequences. This observation has been used in recent years to give conditional lower bounds but also parameterized algorithms. In this paper we carry these results into higher dimensions. We consider Knapsack where items are characterized by multiple properties - given through a vector - and a knapsack that has a capacity vector. The packing must not exceed any of the given capacity constraints. In order to show a similar sub-quadratic lower bound we consider a multidimensional version of (max, +)-convolution. We then consider variants of this problem introduced by Cygan et al. and prove that they are all equivalent in terms of algorithms that allow for a running time sub-quadratic in the number of entries of the array. We further develop a parameterized algorithm to solve higher dimensional Knapsack. The techniques we apply are inspired by an algorithm introduced by Axiotis and Tzamos. We will show that even for higher dimensional Knapsack, we can reduce the problem to convolution on one-dimensional, concave sequences, leading to an 𝒪(dn + dD ⋅ max{(Π_{i=1}^d t_i), t_max log t_max}) algorithm, where D is the number of different weight vectors, t the capacity vector and d is the dimension of the problem. Then, we use the techniques to improve the approach of Eisenbrand and Weismantel to obtain an algorithm for Integer Linear Programming with upper bounds with running time 𝒪(dn) + D ⋅ 𝒪(d Δ)^{d(d+1)} + T_LP. Finally, we give an divide-and-conquer algorithm for ILP with running time n^{d+1} ⋅ O(Δ)^d ⋅ log(|u - 𝓁|_∞).
Cite as

Kilian Grage, Klaus Jansen, and Björn Schumacher. Convolution and Knapsack in Higher Dimensions. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grage_et_al:LIPIcs.WADS.2025.30,
  author =	{Grage, Kilian and Jansen, Klaus and Schumacher, Bj\"{o}rn},
  title =	{{Convolution and Knapsack in Higher Dimensions}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.30},
  URN =		{urn:nbn:de:0030-drops-242618},
  doi =		{10.4230/LIPIcs.WADS.2025.30},
  annote =	{Keywords: Knapsack, Convolution, Integer Linear Programming}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.49
Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game

Authors: Antares Chen, Lorenzo Orecchia, and Erasmo Tani

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Despite there being significant work on developing spectral- [Chan et al., 2018; Lau et al., 2023; Kwok et al., 2022], and metric-embedding-based [Louis and Makarychev, 2016] approximation algorithms for hypergraph conductance, little is known regarding the approximability of other hypergraph partitioning objectives. This work proposes algorithms for a general model of hypergraph partitioning that unifies both undirected and directed versions of many well-studied partitioning objectives. The first contribution of this paper introduces polymatroidal cut functions, a large class of cut functions amenable to approximation algorithms via metric embeddings and routing multicommodity flows. We demonstrate a simple O(√{log n})-approximation, where n is the number of vertices in the hypergraph, for these problems by rounding relaxations to metrics of negative-type. The second contribution of this paper generalizes the cut-matching game framework of Khandekar et al. [Khandekar et al., 2007] to tackle polymatroidal cut functions. This yields an almost-linear time O(log n)-approximation algorithm for standard versions of undirected and directed hypergraph partitioning [Kwok et al., 2022]. A technical contribution of our construction is a novel cut-matching game, which greatly relaxes the set of allowed actions by the cut player and allows for the use of approximate s-t maximum flows by the matching player. We believe this to be of independent interest.
Cite as

Antares Chen, Lorenzo Orecchia, and Erasmo Tani. Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2025.49,
  author =	{Chen, Antares and Orecchia, Lorenzo and Tani, Erasmo},
  title =	{{Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.49},
  URN =		{urn:nbn:de:0030-drops-234261},
  doi =		{10.4230/LIPIcs.ICALP.2025.49},
  annote =	{Keywords: Hypergraph Partitioning, Cut Improvement, Cut-Matching Game}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.51
Weakly Approximating Knapsack in Subquadratic Time

Authors: Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We consider the classic Knapsack problem. Let t and OPT be the capacity and the optimal value, respectively. If one seeks a solution with total profit at least OPT/(1 + ε) and total weight at most t, then Knapsack can be solved in Õ(n + (1/(ε))²) time [Chen, Lian, Mao, and Zhang '24][Mao '24]. This running time is the best possible (up to a logarithmic factor), assuming that (min,+)-convolution cannot be solved in truly subquadratic time [Künnemann, Paturi, and Schneider '17][Cygan, Mucha, Węgrzycki, and Włodarczyk '19]. The same upper and lower bounds hold if one seeks a solution with total profit at least OPT and total weight at most (1 + ε)t. Therefore, it is natural to ask the following question. If one seeks a solution with total profit at least OPT/(1+ε) and total weight at most (1 + ε)t, can Knsapck be solved in Õ(n + (1/(ε))^{2-δ}) time for some constant δ > 0? We answer this open question affirmatively by proposing an Õ(n + (1/(ε))^{7/4})-time algorithm.
Cite as

Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang. Weakly Approximating Knapsack in Subquadratic Time. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2025.51,
  author =	{Chen, Lin and Lian, Jiayi and Mao, Yuchen and Zhang, Guochuan},
  title =	{{Weakly Approximating Knapsack in Subquadratic Time}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{51:1--51:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.51},
  URN =		{urn:nbn:de:0030-drops-234286},
  doi =		{10.4230/LIPIcs.ICALP.2025.51},
  annote =	{Keywords: Knapsack, FPTAS}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.6
Dismountability in Temporal Cliques Revisited

Authors: Daniele Carnevale, Arnaud Casteigts, and Timothée Corsini

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
A temporal graph is a graph whose edges are available only at certain points in time. It is temporally connected if the nodes can reach each other by paths that traverse the edges chronologically (temporal paths). Unlike static graphs, temporal graphs do not always admit small subsets of edges that preserve connectivity (temporal spanners) - there exist temporal graphs with Θ(n²) edges, all of which are critical. In the case of temporal cliques (the underlying graph is complete), spanners of size O(nlog n) are guaranteed. The original proof of this result by Casteigts et al. [ICALP 2019] combines a number of techniques, one of which is called dismountability. In a recent work, Angrick et al. [ESA 2024] simplified the proof and showed, among other things, that a one-sided version of dismountability can replace elegantly the second part of the proof. In this paper, we revisit methodically the dismountability principle. We start by characterizing the structure that a temporal clique must have if it is non 1-hop dismountable, then neither 1-hop nor 2-hop (i.e. non {1,2}-hop) dismountable, and finally non {1,2,3}-hop dismountable. It turns out that if a clique is k-hop dismountable for any other k, then it must also be {1,2,3}-hop dismountable, thus no additional structure can be obtained beyond this point. Interestingly, excluding 1-hop and 2-hop dismountability is already sufficient for reducing the spanner problem from cliques to extremally matched bicliques, where the O(nlog n) result is subsequently obtained. Put together with the strategy of Angrick et al., this entire result can now be recovered using only dismountability. An interesting by-product of our analysis is that any minimal counter-example to the existence of 4n spanners must satisfy the properties of non {1,2,3}-hop dismountable cliques. In the second part, we discuss further connections between dismountability and another technique called pivotability. In particular, we show that if a temporal clique is recursively k-hop dismountable, then it is also pivotable (and thus admits a 2n spanner, whatever k). We also study a family of labelings called full-range that forces both dismountability and pivotability. The latter gives some evidence that large lifetimes could be exploited more generally for the construction of spanners.
Cite as

Daniele Carnevale, Arnaud Casteigts, and Timothée Corsini. Dismountability in Temporal Cliques Revisited. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{carnevale_et_al:LIPIcs.SAND.2025.6,
  author =	{Carnevale, Daniele and Casteigts, Arnaud and Corsini, Timoth\'{e}e},
  title =	{{Dismountability in Temporal Cliques Revisited}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.6},
  URN =		{urn:nbn:de:0030-drops-230591},
  doi =		{10.4230/LIPIcs.SAND.2025.6},
  annote =	{Keywords: Dynamic networks, Temporal graphs, Reachability, Dismountability, Pivotability, Temporal spanners, Full-range graphs}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.3
Temporal Connectivity Augmentation

Authors: Thomas Bellitto, Jules Bouton Popper, and Bruno Escoffier

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
Connectivity in temporal graphs relies on the notion of temporal paths, in which edges follow a chronological order (either strict or non-strict). In this work, we investigate the question of how to make a temporal graph connected. More precisely, we tackle the problem of finding, among a set of proposed temporal edges, the smallest subset such that its addition makes the graph temporally connected (TCA). We study the complexity of this problem and variants, under restricted lifespan of the graph, i.e. the maximum time step in the graph. Our main result on TCA is that for any fixed lifespan at least 2, it is NP-complete in both the strict and non-strict setting. We additionally provide a set of restrictions in the non-strict setting which makes the problem solvable in polynomial time and design an algorithm achieving this complexity. Interestingly, we prove that the source variant (making a given vertex a source in the augmented graph) is as difficult as TCA. On the opposite, we prove that the version where a list of connectivity demands has to be satisfied is solvable in polynomial time, when the size of the list is fixed. Finally, we highlight a variant of the previous case for which even with two pairs the problem is already NP-hard.
Cite as

Thomas Bellitto, Jules Bouton Popper, and Bruno Escoffier. Temporal Connectivity Augmentation. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bellitto_et_al:LIPIcs.SAND.2025.3,
  author =	{Bellitto, Thomas and Popper, Jules Bouton and Escoffier, Bruno},
  title =	{{Temporal Connectivity Augmentation}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.3},
  URN =		{urn:nbn:de:0030-drops-230565},
  doi =		{10.4230/LIPIcs.SAND.2025.3},
  annote =	{Keywords: Temporal graph, temporal connectivity}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.9
Spanner Enumeration for Temporal Graphs

Authors: Kazuhiro Kurita, Andrea Marino, Jason Schoeters, and Takeaki Uno

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
A spanner of a temporal graph is a subset of edges that preserves connectivity over time between vertices. A minimal spanner is one in which no additional edges can be removed without breaking this connectivity. Our focus is on enumerating minimal spanners for a given temporal graph. We explore several variations of this problem based on the type of connectivity that must be maintained, ranging from one-to-all connectivity to one-to-all-to-one, many-to-all, and finally all-to-all connectivity. We establish that these problems become progressively harder: (i) We present a polynomial-delay enumeration algorithm for one-to-all connectivity; (ii) We prove Dual-hardness for both one-to-all-to-one and many-to-all connectivity, even in the restricted case of two-to-all; (iii) Finally, for all-to-all connectivity, we show that enumeration cannot be performed in output-polynomial time unless P = NP.
Cite as

Kazuhiro Kurita, Andrea Marino, Jason Schoeters, and Takeaki Uno. Spanner Enumeration for Temporal Graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kurita_et_al:LIPIcs.SAND.2025.9,
  author =	{Kurita, Kazuhiro and Marino, Andrea and Schoeters, Jason and Uno, Takeaki},
  title =	{{Spanner Enumeration for Temporal Graphs}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.9},
  URN =		{urn:nbn:de:0030-drops-230621},
  doi =		{10.4230/LIPIcs.SAND.2025.9},
  annote =	{Keywords: temporal graphs, temporal spanners, one-to-all connectivity, all-to-all connectivity enumeration, NP-completeness, Dual-hardness, binary partition tree, flashlight search, polynomial delay}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.19
Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms

Authors: Kyriakos Axiotis and Christos Tzamos

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
One of the most fundamental problems in Computer Science is the Knapsack problem. Given a set of n items with different weights and values, it asks to pick the most valuable subset whose total weight is below a capacity threshold T. Despite its wide applicability in various areas in Computer Science, Operations Research, and Finance, the best known running time for the problem is O(T n). The main result of our work is an improved algorithm running in time O(TD), where D is the number of distinct weights. Previously, faster runtimes for Knapsack were only possible when both weights and values are bounded by M and V respectively, running in time O(nMV) [Pisinger, 1999]. In comparison, our algorithm implies a bound of O(n M^2) without any dependence on V, or O(n V^2) without any dependence on M. Additionally, for the unbounded Knapsack problem, we provide an algorithm running in time O(M^2) or O(V^2). Both our algorithms match recent conditional lower bounds shown for the Knapsack problem [Marek Cygan et al., 2017; Marvin Künnemann et al., 2017]. We also initiate a systematic study of general capacitated dynamic programming, of which Knapsack is a core problem. This problem asks to compute the maximum weight path of length k in an edge- or node-weighted directed acyclic graph. In a graph with m edges, these problems are solvable by dynamic programming in time O(k m), and we explore under which conditions the dependence on k can be eliminated. We identify large classes of graphs where this is possible and apply our results to obtain linear time algorithms for the problem of k-sparse Delta-separated sequences. The main technical innovation behind our results is identifying and exploiting concavity that appears in relaxations and subproblems of the tasks we consider.
Cite as

Kyriakos Axiotis and Christos Tzamos. Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{axiotis_et_al:LIPIcs.ICALP.2019.19,
  author =	{Axiotis, Kyriakos and Tzamos, Christos},
  title =	{{Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{19:1--19:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.19},
  URN =		{urn:nbn:de:0030-drops-105952},
  doi =		{10.4230/LIPIcs.ICALP.2019.19},
  annote =	{Keywords: Knapsack, Fine-Grained Complexity, Dynamic Programming}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.149
On the Size and the Approximability of Minimum Temporally Connected Subgraphs

Authors: Kyriakos Axiotis and Dimitris Fotakis

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We consider temporal graphs with discrete time labels and investigate the size and the approximability of minimum temporally connected spanning subgraphs. We present a family of minimally connected temporal graphs with n vertices and Omega(n^2) edges, thus resolving an open question of (Kempe, Kleinberg, Kumar, JCSS 64, 2002) about the existence of sparse temporal connectivity certificates. Next, we consider the problem of computing a minimum weight subset of temporal edges that preserve connectivity of a given temporal graph either from a given vertex r (r-MTC problem) or among all vertex pairs (MTC problem). We show that the approximability of r-MTC is closely related to the approximability of Directed Steiner Tree and that r-MTC can be solved in polynomial time if the underlying graph has bounded treewidth. We also show that the best approximation ratio for MTC is at least O(2^{log^{1-epsilon}(n)} and at most O(min{n^{1+epsilon},(Delta*M)^{2/3+epsilon}), for any constant epsilon > 0, where M is the number of temporal edges and Delta is the maximum degree of the underlying graph. Furthermore, we prove that the unweighted version of MTC is APX-hard and that MTC is efficiently solvable in trees and 2-approximable in cycles.
Cite as

Kyriakos Axiotis and Dimitris Fotakis. On the Size and the Approximability of Minimum Temporally Connected Subgraphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 149:1-149:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{axiotis_et_al:LIPIcs.ICALP.2016.149,
  author =	{Axiotis, Kyriakos and Fotakis, Dimitris},
  title =	{{On the Size and the Approximability of Minimum Temporally Connected Subgraphs}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{149:1--149:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.149},
  URN =		{urn:nbn:de:0030-drops-62936},
  doi =		{10.4230/LIPIcs.ICALP.2016.149},
  annote =	{Keywords: Temporal Graphs, Temporal Connectivity, Approximation Algorithms}
}
  • Refine by Type
  • 8 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 6 2025
  • 1 2019
  • 1 2016

  • Refine by Author
  • 2 Axiotis, Kyriakos
  • 1 Bellitto, Thomas
  • 1 Carnevale, Daniele
  • 1 Casteigts, Arnaud
  • 1 Chen, Antares
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graph enumeration
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Networks → Network dynamics
  • Show More...

  • Refine by Keyword
  • 3 Knapsack
  • 1 Approximation Algorithms
  • 1 Convolution
  • 1 Cut Improvement
  • 1 Cut-Matching Game
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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