10 Search Results for "Spinrad, Jeremy P."

Document
DOI: 10.4230/LIPIcs.SEA.2024.3
Practical Minimum Path Cover

Authors: Manuel Cáceres, Brendan Mumey, Santeri Toivonen, and Alexandru I. Tomescu

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
Computing a minimum path cover (MPC) of a directed acyclic graph (DAG) is a fundamental problem with a myriad of applications, including reachability. Although it is known how to solve the problem by a simple reduction to minimum flow, recent theoretical advances exploit this idea to obtain algorithms parameterized by the number of paths of an MPC, known as the width. These results obtain fast [Mäkinen et al., TALG 2019] and even linear time [Cáceres et al., SODA 2022] algorithms in the small-width regime. In this paper, we present the first publicly available high-performance implementation of state-of-the-art MPC algorithms, including the parameterized approaches. Our experiments on random DAGs show that parameterized algorithms are orders-of-magnitude faster on dense graphs. Additionally, we present new fast pre-processing heuristics based on transitive edge sparsification. We show that our heuristics improve MPC-solvers by orders of magnitude.
Cite as

Manuel Cáceres, Brendan Mumey, Santeri Toivonen, and Alexandru I. Tomescu. Practical Minimum Path Cover. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{caceres_et_al:LIPIcs.SEA.2024.3,
  author =	{C\'{a}ceres, Manuel and Mumey, Brendan and Toivonen, Santeri and Tomescu, Alexandru I.},
  title =	{{Practical Minimum Path Cover}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.3},
  URN =		{urn:nbn:de:0030-drops-203687},
  doi =		{10.4230/LIPIcs.SEA.2024.3},
  annote =	{Keywords: minimum path cover, directed acyclic graph, maximum flow, parameterized algorithms, edge sparsification, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2024.33
State Canonization and Early Pruning in Width-Based Automated Theorem Proving

Authors: Mateus de Oliveira Oliveira and Farhad Vadiee

Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)

Abstract
Width-based automated theorem proving is a framework where counter-examples for graph theoretic conjectures are searched width-wise relative to some graph width measure, such as treewidth or pathwidth. In a recent work it has been shown that dynamic programming algorithms operating on tree decompositions can be combined together with the purpose of width-based theorem proving. This approach can be used to show that several long-standing conjectures in graph theory can be tested in time 2^{2^{k^{O(1)}}} on the class of graphs of treewidth at most k. In this work, we give the first steps towards evaluating the viability of this framework from a practical standpoint. At the same time, we advance the framework in two directions. First, we introduce a state-canonization technique that significantly reduces the number of states evaluated during the search for a counter-example of the conjecture. Second, we introduce an early-pruning technique that can be applied in the study of conjectures of the form ℙ₁ → ℙ₂, for graph properties ℙ₁ and ℙ₂, where ℙ₁ is a property closed under subgraphs. As a concrete application, we use our framework in the study of graph theoretic conjectures related to coloring triangle free graphs. In particular, our algorithm is able to show that Reed’s conjecture for triangle free graphs is valid on the class of graphs of pathwidth at most 5, and on graphs of treewidth at most 3. Perhaps more interestingly, our algorithm is able to construct in a completely automated way counter-examples for non-valid strengthenings of Reed’s conjecture. These are the first results showing that width-based automated theorem proving is a promising avenue in the study of graph-theoretic conjectures.
Cite as

Mateus de Oliveira Oliveira and Farhad Vadiee. State Canonization and Early Pruning in Width-Based Automated Theorem Proving. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{deoliveiraoliveira_et_al:LIPIcs.FSCD.2024.33,
  author =	{de Oliveira Oliveira, Mateus and Vadiee, Farhad},
  title =	{{State Canonization and Early Pruning in Width-Based Automated Theorem Proving}},
  booktitle =	{9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-323-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{299},
  editor =	{Rehof, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.33},
  URN =		{urn:nbn:de:0030-drops-203622},
  doi =		{10.4230/LIPIcs.FSCD.2024.33},
  annote =	{Keywords: Width-Based Automated Theorem Proving, Dynamic Programming, Parameterized Complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.51
Computing Tree Decompositions with Small Independence Number

Authors: Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition of it. Several NP-hard graph problems, like maximum weight independent set, can be solved in time n^𝒪(k) if the input n-vertex graph is given together with a tree decomposition of independence number k. Yolov in [SODA 2018] gave an algorithm that given an n-vertex graph G and an integer k, in time n^𝒪(k³) either constructs a tree decomposition of G whose independence number is 𝒪(k³) or correctly reports that the tree-independence number of G is larger than k. In this paper, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. More precisely, our algorithm runs in time 2^𝒪(k²) n^𝒪(k) and either outputs a tree decomposition of G with independence number at most 8k, or determines that the tree-independence number of G is larger than k. This implies 2^𝒪(k²) n^𝒪(k)-time algorithms for various problems, like maximum weight independent set, parameterized by the tree-independence number k without needing the decomposition as an input. Assuming Gap-ETH, an n^Ω(k) factor in the running time is unavoidable for any approximation algorithm for the tree-independence number. Our second result is that the exact computation of the tree-independence number is para-NP-hard: We show that for every constant k ≥ 4 it is NP-hard to decide if a given graph has the tree-independence number at most k.
Cite as

Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič. Computing Tree Decompositions with Small Independence Number. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dallard_et_al:LIPIcs.ICALP.2024.51,
  author =	{Dallard, Cl\'{e}ment and Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka and Milani\v{c}, Martin},
  title =	{{Computing Tree Decompositions with Small Independence Number}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{51:1--51:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.51},
  URN =		{urn:nbn:de:0030-drops-201945},
  doi =		{10.4230/LIPIcs.ICALP.2024.51},
  annote =	{Keywords: tree-independence number, approximation, parameterized algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.31
Tight Bounds on Adjacency Labels for Monotone Graph Classes

Authors: Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
A class of graphs admits an adjacency labeling scheme of size b(n), if the vertices in each of its n-vertex graphs can be assigned binary strings (called labels) of length b(n) so that the adjacency of two vertices can be determined solely from their labels. We give bounds on the size of adjacency labels for every family of monotone (i.e., subgraph-closed) classes with a "well-behaved" growth function between 2^Ω(n log n) and 2^O(n^{2-δ}) for any δ > 0. Specifically, we show that for any function f: ℕ → ℝ satisfying log n ⩽ f(n) ⩽ n^{1-δ} for any fixed δ > 0, and some sub-multiplicativity condition, there are monotone graph classes with growth 2^O(nf(n)) that do not admit adjacency labels of size at most f(n) log n. On the other hand, any such class does admit adjacency labels of size O(f(n)log n). Surprisingly this bound is a Θ(log n) factor away from the information-theoretic bound of Ω(f(n)). Our bounds are tight upto constant factors, and the special case when f = log implies that the recently-refuted Implicit Graph Conjecture [Hatami and Hatami, FOCS 2022] also fails within monotone classes. We further show that the Implicit Graph Conjecture holds for all monotone small classes. In other words, any monotone class with growth rate at most n! cⁿ for some constant c > 0, admits adjacency labels of information-theoretic order optimal size. In fact, we show a more general result that is of independent interest: any monotone small class of graphs has bounded degeneracy. We conjecture that the Implicit Graph Conjecture holds for all hereditary small classes.
Cite as

Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii. Tight Bounds on Adjacency Labels for Monotone Graph Classes. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ICALP.2024.31,
  author =	{Bonnet, \'{E}douard and Duron, Julien and Sylvester, John and Zamaraev, Viktor and Zhukovskii, Maksim},
  title =	{{Tight Bounds on Adjacency Labels for Monotone Graph Classes}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{31:1--31:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.31},
  URN =		{urn:nbn:de:0030-drops-201741},
  doi =		{10.4230/LIPIcs.ICALP.2024.31},
  annote =	{Keywords: Adjacency labeling, degeneracy, monotone classes, small classes, factorial classes, implicit graph conjecture}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.69
Double Threshold Digraphs

Authors: Peter Hamburger, Ross M. McConnell, Attila Pór, Jeremy P. Spinrad, and Zhisheng Xu

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
A semiorder is a model of preference relations where each element x is associated with a utility value alpha(x), and there is a threshold t such that y is preferred to x iff alpha(y) - alpha(x) > t. These are motivated by the notion that there is some uncertainty in the utility values we assign an object or that a subject may be unable to distinguish a preference between objects whose values are close. However, they fail to model the well-known phenomenon that preferences are not always transitive. Also, if we are uncertain of the utility values, it is not logical that preference is determined absolutely by a comparison of them with an exact threshold. We propose a new model in which there are two thresholds, t_1 and t_2; if the difference alpha(y) - alpha(x) is less than t_1, then y is not preferred to x; if the difference is greater than t_2 then y is preferred to x; if it is between t_1 and t_2, then y may or may not be preferred to x. We call such a relation a (t_1,t_2) double-threshold semiorder, and the corresponding directed graph G = (V,E) a (t_1,t_2) double-threshold digraph. Every directed acyclic graph is a double-threshold digraph; increasing bounds on t_2/t_1 give a nested hierarchy of subclasses of the directed acyclic graphs. In this paper we characterize the subclasses in terms of forbidden subgraphs, and give algorithms for finding an assignment of utility values that explains the relation in terms of a given (t_1,t_2) or else produces a forbidden subgraph, and finding the minimum value lambda of t_2/t_1 that is satisfiable for a given directed acyclic graph. We show that lambda gives a useful measure of the complexity of a directed acyclic graph with respect to several optimization problems that are NP-hard on arbitrary directed acyclic graphs.
Cite as

Peter Hamburger, Ross M. McConnell, Attila Pór, Jeremy P. Spinrad, and Zhisheng Xu. Double Threshold Digraphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 69:1-69:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hamburger_et_al:LIPIcs.MFCS.2018.69,
  author =	{Hamburger, Peter and McConnell, Ross M. and P\'{o}r, Attila and Spinrad, Jeremy P. and Xu, Zhisheng},
  title =	{{Double Threshold Digraphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{69:1--69:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.69},
  URN =		{urn:nbn:de:0030-drops-96519},
  doi =		{10.4230/LIPIcs.MFCS.2018.69},
  annote =	{Keywords: posets, preference relations, approximation algorithms}
}
Document
DOI: 10.4230/DagSemProc.07211.1
07211 Abstracts Collection – Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes

Authors: Andreas Brandstädt, Klaus Jansen, Dieter Kratsch, and Jeremy P. Spinrad

Published in: Dagstuhl Seminar Proceedings, Volume 7211, Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes (2007)

Abstract
From May 20 to May 25, 2007, the Dagstuhl Seminar 07211 ``Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Andreas Brandstädt, Klaus Jansen, Dieter Kratsch, and Jeremy P. Spinrad. 07211 Abstracts Collection – Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes. In Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes. Dagstuhl Seminar Proceedings, Volume 7211, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{brandstadt_et_al:DagSemProc.07211.1,
  author =	{Brandst\"{a}dt, Andreas and Jansen, Klaus and Kratsch, Dieter and Spinrad, Jeremy P.},
  title =	{{07211 Abstracts Collection – Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes}},
  booktitle =	{Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7211},
  editor =	{Andreas Brandst\"{a}dt and Klaus Jansen and Dieter Kratsch and Jeremy P. Spinrad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07211.1},
  URN =		{urn:nbn:de:0030-drops-12697},
  doi =		{10.4230/DagSemProc.07211.1},
  annote =	{Keywords: Graph theory, approximation algorithms, certifying algorithms, exact algorithms}
}
Document
DOI: 10.4230/DagSemProc.07211.2
Linear-time certifying recognition for partitioned probe cographs

Authors: Van Bang Le and H.N. de Ridder

Published in: Dagstuhl Seminar Proceedings, Volume 7211, Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes (2007)

Abstract
Cographs are those graphs without induced path on four vetices. A graph $G=(V, E)$ with a partition $V=Pcup N$ where $N$ is an independent set is a partitioned probe cograph if one can add new edges between certain vertices in $N$ in such a way that the graph obtained is a cograph. We characterize partitioned probe cographs in terms of five forbidden induced subgraphs. Using this characterization, we give a linear-time recognition algorithm for partitioned probe cographs. Our algorithm produces a certificate for membership that can be checked in linear time and a certificate for non-membership that can be checked in sublinear time.
Cite as

Van Bang Le and H.N. de Ridder. Linear-time certifying recognition for partitioned probe cographs. In Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes. Dagstuhl Seminar Proceedings, Volume 7211, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{le_et_al:DagSemProc.07211.2,
  author =	{Le, Van Bang and de Ridder, H.N.},
  title =	{{Linear-time certifying recognition for partitioned probe cographs}},
  booktitle =	{Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7211},
  editor =	{Andreas Brandst\"{a}dt and Klaus Jansen and Dieter Kratsch and Jeremy P. Spinrad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07211.2},
  URN =		{urn:nbn:de:0030-drops-12703},
  doi =		{10.4230/DagSemProc.07211.2},
  annote =	{Keywords: Cograph, probe cograph, certifying graph algorithm}
}
Document
DOI: 10.4230/DagSemProc.04221.1
04221 Abstracts Collection – Robust and Approximative Algorithms on Particular Graph Classes

Authors: Andreas Brandstädt, Derek G. Corneil, Klaus Jansen, and Jeremy P. Spinrad

Published in: Dagstuhl Seminar Proceedings, Volume 4221, Robust and Approximative Algorithms an Particular Graph Classes (2005)

Abstract
From 23.05.04 to 28.05.04, the Dagstuhl Seminar 04221 ``Robust and Approximative Algorithms on Particular Graph Classes'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Andreas Brandstädt, Derek G. Corneil, Klaus Jansen, and Jeremy P. Spinrad. 04221 Abstracts Collection – Robust and Approximative Algorithms on Particular Graph Classes. In Robust and Approximative Algorithms an Particular Graph Classes. Dagstuhl Seminar Proceedings, Volume 4221, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{brandstadt_et_al:DagSemProc.04221.1,
  author =	{Brandst\"{a}dt, Andreas and Corneil, Derek G. and Jansen, Klaus and Spinrad, Jeremy P.},
  title =	{{04221 Abstracts Collection – Robust and Approximative Algorithms on Particular Graph Classes}},
  booktitle =	{Robust and Approximative Algorithms an Particular Graph Classes},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4221},
  editor =	{Andreas Brandst\"{a}dt and Derek G. Corneil and Klaus Jansen and Jeremy P. Spinrad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04221.1},
  URN =		{urn:nbn:de:0030-drops-2732},
  doi =		{10.4230/DagSemProc.04221.1},
  annote =	{Keywords: Graph algorithms, graph classes, graph algorithms, robust algorithms, approximation}
}
Document
DOI: 10.4230/DagSemRep.312
Graph Decompositions and Algorithmic Applications (Dagstuhl Seminar 01251)

Authors: Andreas Brandstädt and Jeremy P. Spinrad

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Andreas Brandstädt and Jeremy P. Spinrad. Graph Decompositions and Algorithmic Applications (Dagstuhl Seminar 01251). Dagstuhl Seminar Report 312, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{brandstadt_et_al:DagSemRep.312,
  author =	{Brandst\"{a}dt, Andreas and Spinrad, Jeremy P.},
  title =	{{Graph Decompositions and Algorithmic Applications (Dagstuhl Seminar 01251)}},
  pages =	{1--20},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{312},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.312},
  URN =		{urn:nbn:de:0030-drops-151962},
  doi =		{10.4230/DagSemRep.312},
}
Document
DOI: 10.4230/DagSemRep.241
Graph Decompositions and Algorithmic Applications (Dagstuhl Seminar 99231)

Authors: Andreas Brandstädt, Stephan Olariu, and Jeremy P. Spinrad

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Andreas Brandstädt, Stephan Olariu, and Jeremy P. Spinrad. Graph Decompositions and Algorithmic Applications (Dagstuhl Seminar 99231). Dagstuhl Seminar Report 241, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1999)

Copy BibTex To Clipboard

@TechReport{brandstadt_et_al:DagSemRep.241,
  author =	{Brandst\"{a}dt, Andreas and Olariu, Stephan and Spinrad, Jeremy P.},
  title =	{{Graph Decompositions and Algorithmic Applications (Dagstuhl Seminar 99231)}},
  pages =	{1--20},
  ISSN =	{1619-0203},
  year =	{1999},
  type = 	{Dagstuhl Seminar Report},
  number =	{241},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.241},
  URN =		{urn:nbn:de:0030-drops-151276},
  doi =		{10.4230/DagSemRep.241},
}
  • Refine by Author
  • 5 Spinrad, Jeremy P.
  • 4 Brandstädt, Andreas
  • 2 Jansen, Klaus
  • 1 Bonnet, Édouard
  • 1 Corneil, Derek G.
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 2 approximation
  • 2 approximation algorithms
  • 2 parameterized algorithms
  • 1 Adjacency labeling
  • 1 Cograph
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 4 2024
  • 2 2007
  • 1 1999
  • 1 2002
  • 1 2005
  • Show More...

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact