2 Search Results for "Nikolopoulos, Stavros D."


Document
An Experimental Study of Algorithms for Packing Arborescences

Authors: Loukas Georgiadis, Dionysios Kefallinos, Anna Mpanti, and Stavros D. Nikolopoulos

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)


Abstract
A classic result of Edmonds states that the maximum number of edge-disjoint arborescences of a directed graph G, rooted at a designated vertex s, equals the minimum cardinality c_G(s) of an s-cut of G. This concept is related to the edge connectivity λ(G) of a strongly connected directed graph G, defined as the minimum number of edges whose deletion leaves a graph that is not strongly connected. In this paper, we address the question of how efficiently we can compute a maximum packing of edge-disjoint arborescences in practice, compared to the time required to determine the edge connectivity of a graph. To that end, we explore the design space of efficient algorithms for packing arborescences of a directed graph in practice and conduct a thorough empirical study to highlight the merits and weaknesses of each technique. In particular, we present an efficient implementation of Gabow’s arborescence packing algorithm and provide a simple but efficient heuristic that significantly improves its running time in practice.

Cite as

Loukas Georgiadis, Dionysios Kefallinos, Anna Mpanti, and Stavros D. Nikolopoulos. An Experimental Study of Algorithms for Packing Arborescences. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 14:1-14:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.SEA.2022.14,
  author =	{Georgiadis, Loukas and Kefallinos, Dionysios and Mpanti, Anna and Nikolopoulos, Stavros D.},
  title =	{{An Experimental Study of Algorithms for Packing Arborescences}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.14},
  URN =		{urn:nbn:de:0030-drops-165480},
  doi =		{10.4230/LIPIcs.SEA.2022.14},
  annote =	{Keywords: Arborescences, Edge Connectivity, Graph Algorithms}
}
Document
Polynomial Fixed-parameter Algorithms: A Case Study for Longest Path on Interval Graphs

Authors: Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)


Abstract
We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomial time. The main motivation is to get more efficient algorithms for problems with unattractive polynomial running times. Here, we focus on a fundamental graph problem: Longest Path; it is NP-hard in general but known to be solvable in O(n^4) time on n-vertex interval graphs. We show how to solve Longest Path on Interval Graphs, parameterized by vertex deletion number k to proper interval graphs, in O(k^9n) time. Notably, Longest Path is trivially solvable in linear time on proper interval graphs, and the parameter value k can be approximated up to a factor of 4 in linear time. From a more general perspective, we believe that using parameterized complexity analysis for polynomial-time solvable problems offers a very fertile ground for future studies for all sorts of algorithmic problems. It may enable a refined understanding of efficiency aspects for polynomial-time solvable problems, similarly to what classical parameterized complexity analysis does for NP-hard problems.

Cite as

Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. Polynomial Fixed-parameter Algorithms: A Case Study for Longest Path on Interval Graphs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 102-113, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{giannopoulou_et_al:LIPIcs.IPEC.2015.102,
  author =	{Giannopoulou, Archontia C. and Mertzios, George B. and Niedermeier, Rolf},
  title =	{{Polynomial Fixed-parameter Algorithms: A Case Study for Longest Path on Interval Graphs}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{102--113},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.102},
  URN =		{urn:nbn:de:0030-drops-55750},
  doi =		{10.4230/LIPIcs.IPEC.2015.102},
  annote =	{Keywords: fixed-parameter algorithm, preprocessing, data reduction, polynomial-time algorithm, longest path problem, interval graphs, proper interval vertex del}
}
  • Refine by Author
  • 1 Georgiadis, Loukas
  • 1 Giannopoulou, Archontia C.
  • 1 Kefallinos, Dionysios
  • 1 Mertzios, George B.
  • 1 Mpanti, Anna
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Arborescences
  • 1 Edge Connectivity
  • 1 Graph Algorithms
  • 1 data reduction
  • 1 fixed-parameter algorithm
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2022

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