8 Search Results for "Matias, Pedro"

Document
DOI: 10.4230/LIPIcs.ESA.2025.69
Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing

Authors: David Eppstein, Michael T. Goodrich, and Songyu (Alfred) Liu

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We provide the first approximation quality guarantees for the Cuthull-McKee heuristic for reordering symmetric matrices to have low bandwidth, and we provide an algorithm for reconstructing bounded-bandwidth graphs from distance oracles with near-linear query complexity. To prove these results we introduce a new width parameter, BFS width, and we prove polylogarithmic upper and lower bounds on the BFS width of graphs of bounded bandwidth. Unlike other width parameters, such as bandwidth, pathwidth, and treewidth, BFS width can easily be computed in polynomial time. Bounded BFS width implies bounded bandwidth, pathwidth, and treewidth, which in turn imply fixed-parameter tractable algorithms for many problems that are NP-hard for general graphs. In addition to their applications to matrix ordering, we also provide applications of BFS width to graph reconstruction, to reconstruct graphs from distance queries, and graph drawing, to construct arc diagrams of small height.
Cite as

David Eppstein, Michael T. Goodrich, and Songyu (Alfred) Liu. Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 69:1-69:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.ESA.2025.69,
  author =	{Eppstein, David and Goodrich, Michael T. and Liu, Songyu (Alfred)},
  title =	{{Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{69:1--69:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.69},
  URN =		{urn:nbn:de:0030-drops-245373},
  doi =		{10.4230/LIPIcs.ESA.2025.69},
  annote =	{Keywords: Graph algorithms, graph theory, graph width, bandwidth, treewidth}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.19
Polychromatic Coloring of Tuples in Hypergraphs

Authors: Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, and Miloš Stojaković

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
A hypergraph H consists of a set V of vertices and a set E of hyperedges that are subsets of V. A t-tuple of H is a subset of t vertices of V. A t-tuple k-coloring of H is a mapping of its t-tuples into k colors. A coloring is called (t,k,f)-polychromatic if each hyperedge of E that has at least f vertices contains tuples of all the k colors. Let f_H(t,k) be the minimum f such that H has a (t,k,f)-polychromatic coloring. For a family of hypergraphs ℋ let f_H(t,k) be the maximum f_H(t,k) over all hypergraphs H in H. Determining f_H(t,k) has been an active research direction in recent years. This is challenging even for t = 1. We present several new results in this direction for t ≥ 2. - Let H be the family of hypergraphs H that is obtained by taking any set P of points in ℝ², setting V: = P and E: = {d ∩ P: d is a disk in ℝ²}. We prove that f_ H(2,k) ≤ 3.7^k, that is, the pairs of points (2-tuples) can be k-colored such that any disk containing at least 3.7^k points has pairs of all colors. We generalize this result to points and balls in higher dimensions. - For the family H of hypergraphs that are defined by grid vertices and axis-parallel rectangles in the plane, we show that f_H(2,k) ≤ √{ck ln k} for some constant c. We then generalize this to higher dimensions, to other shapes, and to tuples of larger size. - For the family H of shrinkable hypergraphs of VC-dimension at most d we prove that f_ H(d+1,k) ≤ c^k for some constant c = c(d). Towards this bound, we obtain a result of independent interest: Every hypergraph with n vertices and with VC-dimension at most d has a (d+1)-tuple T of depth at least n/c, i.e., any hyperedge that contains T also contains n/c other vertices. - For the relationship between t-tuple coloring and vertex coloring in any hypergraph H we establish the inequality 1/e⋅ tk^{1/t} ≤ f_H(t,k) ≤ f_H(1,tk^{1/t}). For the special case of k = 2, referred to as the bichromatic coloring, we prove that t+1 ≤ f_H(t,2) ≤ max{f_H(1,2), t+1}; this improves upon the previous best known upper bound. - We study the relationship between tuple coloring and epsilon nets. In particular we show that if f_H(1,k) = O(k) for a hypergraph H with n vertices, then for any 0 < ε < 1 the t-tuples of H can be partitioned into Ω((εn/t)^t) ε-t-nets. This bound is tight when t is a constant.
Cite as

Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, and Miloš Stojaković. Polychromatic Coloring of Tuples in Hypergraphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SoCG.2025.19,
  author =	{Biniaz, Ahmad and De Carufel, Jean-Lou and Maheshwari, Anil and Smid, Michiel and Smorodinsky, Shakhar and Stojakovi\'{c}, Milo\v{s}},
  title =	{{Polychromatic Coloring of Tuples in Hypergraphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.19},
  URN =		{urn:nbn:de:0030-drops-231718},
  doi =		{10.4230/LIPIcs.SoCG.2025.19},
  annote =	{Keywords: Hypergraph Coloring, Polychromatic Coloring, Geometric Hypergraphs, Cover Decomposable Hypergraphs, Epsilon Nets}
}
Document
Survey
DOI: 10.4230/TGDK.1.1.11
How Does Knowledge Evolve in Open Knowledge Graphs?

Authors: Axel Polleres, Romana Pernisch, Angela Bonifati, Daniele Dell'Aglio, Daniil Dobriy, Stefania Dumbrava, Lorena Etcheverry, Nicolas Ferranti, Katja Hose, Ernesto Jiménez-Ruiz, Matteo Lissandrini, Ansgar Scherp, Riccardo Tommasini, and Johannes Wachs

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
Openly available, collaboratively edited Knowledge Graphs (KGs) are key platforms for the collective management of evolving knowledge. The present work aims t o provide an analysis of the obstacles related to investigating and processing specifically this central aspect of evolution in KGs. To this end, we discuss (i) the dimensions of evolution in KGs, (ii) the observability of evolution in existing, open, collaboratively constructed Knowledge Graphs over time, and (iii) possible metrics to analyse this evolution. We provide an overview of relevant state-of-the-art research, ranging from metrics developed for Knowledge Graphs specifically to potential methods from related fields such as network science. Additionally, we discuss technical approaches - and their current limitations - related to storing, analysing and processing large and evolving KGs in terms of handling typical KG downstream tasks.
Cite as

Axel Polleres, Romana Pernisch, Angela Bonifati, Daniele Dell'Aglio, Daniil Dobriy, Stefania Dumbrava, Lorena Etcheverry, Nicolas Ferranti, Katja Hose, Ernesto Jiménez-Ruiz, Matteo Lissandrini, Ansgar Scherp, Riccardo Tommasini, and Johannes Wachs. How Does Knowledge Evolve in Open Knowledge Graphs?. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 11:1-11:59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{polleres_et_al:TGDK.1.1.11,
  author =	{Polleres, Axel and Pernisch, Romana and Bonifati, Angela and Dell'Aglio, Daniele and Dobriy, Daniil and Dumbrava, Stefania and Etcheverry, Lorena and Ferranti, Nicolas and Hose, Katja and Jim\'{e}nez-Ruiz, Ernesto and Lissandrini, Matteo and Scherp, Ansgar and Tommasini, Riccardo and Wachs, Johannes},
  title =	{{How Does Knowledge Evolve in Open Knowledge Graphs?}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{11:1--11:59},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.11},
  URN =		{urn:nbn:de:0030-drops-194855},
  doi =		{10.4230/TGDK.1.1.11},
  annote =	{Keywords: KG evolution, temporal KG, versioned KG, dynamic KG}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.30
Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs

Authors: David Eppstein and Daniel Frishberg

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
We give a new rapid mixing result for a natural random walk on the independent sets of a graph G. We show that when G has bounded treewidth, this random walk - known as the Glauber dynamics for the hardcore model - mixes rapidly for all fixed values of the standard parameter λ > 0, giving a simple alternative to existing sampling algorithms for these structures. We also show rapid mixing for analogous Markov chains on dominating sets, b-edge covers, b-matchings, maximal independent sets, and maximal b-matchings. (For b-matchings, maximal independent sets, and maximal b-matchings we also require bounded degree.) Our results imply simpler alternatives to known algorithms for the sampling and approximate counting problems in these graphs. We prove our results by applying a divide-and-conquer framework we developed in a previous paper, as an alternative to the projection-restriction technique introduced by Jerrum, Son, Tetali, and Vigoda. We extend this prior framework to handle chains for which the application of that framework is not straightforward, strengthening existing results by Dyer, Goldberg, and Jerrum and by Heinrich for the Glauber dynamics on q-colorings of graphs of bounded treewidth and bounded degree.
Cite as

David Eppstein and Daniel Frishberg. Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.ISAAC.2023.30,
  author =	{Eppstein, David and Frishberg, Daniel},
  title =	{{Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.30},
  URN =		{urn:nbn:de:0030-drops-193324},
  doi =		{10.4230/LIPIcs.ISAAC.2023.30},
  annote =	{Keywords: Glauber dynamics, mixing time, projection-restriction, multicommodity flow}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.4
Mapping Networks via Parallel kth-Hop Traceroute Queries

Authors: Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
For a source node, v, and target node, w, the traceroute command iteratively issues "kth-hop" queries, for k = 1, 2, … , δ(v,w), which return the name of the kth vertex on a shortest path from v to w, where δ(v,w) is the distance between v and w, that is, the number of edges in a shortest-path from v to w. The traceroute command is often used for network mapping applications, the study of the connectivity of networks, and it has been studied theoretically with respect to biases it introduces for network mapping when only a subset of nodes in the network can be the source of traceroute queries. In this paper, we provide efficient network mapping algorithms, that are based on kth-hop traceroute queries. Our results include an algorithm that runs in a constant number of parallel rounds with a subquadratic number of queries under reasonable assumptions about the sampling coverage of the nodes that may issue kth-hop traceroute queries. In addition, we introduce a number of new algorithmic techniques, including a high-probability parametric parallelization of a graph clustering technique of Thorup and Zwick, which may be of independent interest.
Cite as

Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Mapping Networks via Parallel kth-Hop Traceroute Queries. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{afshar_et_al:LIPIcs.STACS.2022.4,
  author =	{Afshar, Ramtin and Goodrich, Michael T. and Matias, Pedro and Osegueda, Martha C.},
  title =	{{Mapping Networks via Parallel kth-Hop Traceroute Queries}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{4:1--4:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.4},
  URN =		{urn:nbn:de:0030-drops-158142},
  doi =		{10.4230/LIPIcs.STACS.2022.4},
  annote =	{Keywords: Network mapping, graph algorithms, parallel algorithms, distributed computing, query complexity, kth-hop queries}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.3
Reconstructing Biological and Digital Phylogenetic Trees in Parallel

Authors: Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
In this paper, we study the parallel query complexity of reconstructing biological and digital phylogenetic trees from simple queries involving their nodes. This is motivated from computational biology, data protection, and computer security settings, which can be abstracted in terms of two parties, a responder, Alice, who must correctly answer queries of a given type regarding a degree-d tree, T, and a querier, Bob, who issues batches of queries, with each query in a batch being independent of the others, so as to eventually infer the structure of T. We show that a querier can efficiently reconstruct an n-node degree-d tree, T, with a logarithmic number of rounds and quasilinear number of queries, with high probability, for various types of queries, including relative-distance queries and path queries. Our results are all asymptotically optimal and improve the asymptotic (sequential) query complexity for one of the problems we study. Moreover, through an experimental analysis using both real-world and synthetic data, we provide empirical evidence that our algorithms provide significant parallel speedups while also improving the total query complexities for the problems we study.
Cite as

Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Reconstructing Biological and Digital Phylogenetic Trees in Parallel. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{afshar_et_al:LIPIcs.ESA.2020.3,
  author =	{Afshar, Ramtin and Goodrich, Michael T. and Matias, Pedro and Osegueda, Martha C.},
  title =	{{Reconstructing Biological and Digital Phylogenetic Trees in Parallel}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{3:1--3:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.3},
  URN =		{urn:nbn:de:0030-drops-128696},
  doi =		{10.4230/LIPIcs.ESA.2020.3},
  annote =	{Keywords: Tree Reconstruction, Parallel Algorithms, Privacy, Phylogenetic Trees, Data Structures, Hierarchical Clustering}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.51
New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs

Authors: Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen Kobourov, Pedro Matias, and Valentin Polishchuk

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We use it to construct the greedy multi-fragment tour for Euclidean TSP in O(n log n) time in any fixed dimension and for Steiner TSP in planar graphs in O(n sqrt(n)log n) time; we compute motorcycle graphs, a central step in straight skeleton algorithms, in O(n^(4/3+epsilon)) time for any epsilon>0.
Cite as

Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen Kobourov, Pedro Matias, and Valentin Polishchuk. New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 51:1-51:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mamano_et_al:LIPIcs.ISAAC.2019.51,
  author =	{Mamano, Nil and Efrat, Alon and Eppstein, David and Frishberg, Daniel and Goodrich, Michael T. and Kobourov, Stephen and Matias, Pedro and Polishchuk, Valentin},
  title =	{{New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{51:1--51:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.51},
  URN =		{urn:nbn:de:0030-drops-115477},
  doi =		{10.4230/LIPIcs.ISAAC.2019.51},
  annote =	{Keywords: Nearest-neighbors, Nearest-neighbor chain, motorcycle graph, straight skeleton, multi-fragment algorithm, Euclidean TSP, Steiner TSP}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.54
Tracking Paths in Planar Graphs

Authors: David Eppstein, Michael T. Goodrich, James A. Liu, and Pedro Matias

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We consider the NP-complete problem of tracking paths in a graph, first introduced by Banik et al. [Banik et al., 2017]. Given an undirected graph with a source s and a destination t, find the smallest subset of vertices whose intersection with any s-t path results in a unique sequence. In this paper, we show that this problem remains NP-complete when the graph is planar and we give a 4-approximation algorithm in this setting. We also show, via Courcelle’s theorem, that it can be solved in linear time for graphs of bounded-clique width, when its clique decomposition is given in advance.
Cite as

David Eppstein, Michael T. Goodrich, James A. Liu, and Pedro Matias. Tracking Paths in Planar Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.ISAAC.2019.54,
  author =	{Eppstein, David and Goodrich, Michael T. and Liu, James A. and Matias, Pedro},
  title =	{{Tracking Paths in Planar Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{54:1--54:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.54},
  URN =		{urn:nbn:de:0030-drops-115500},
  doi =		{10.4230/LIPIcs.ISAAC.2019.54},
  annote =	{Keywords: Approximation Algorithm, Courcelle’s Theorem, Clique-Width, Planar, 3-SAT, Graph Algorithms, NP-Hardness}
}
  • Refine by Type
  • 8 Document/PDF
  • 3 Document/HTML

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

  • Refine by Author
  • 5 Goodrich, Michael T.
  • 4 Eppstein, David
  • 4 Matias, Pedro
  • 2 Afshar, Ramtin
  • 2 Frishberg, Daniel
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 2 Mathematics of computing → Graph theory
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Information systems → Data streaming
  • 1 Information systems → Graph-based database models
  • Show More...

  • Refine by Keyword
  • 1 3-SAT
  • 1 Approximation Algorithm
  • 1 Clique-Width
  • 1 Courcelle’s Theorem
  • 1 Cover Decomposable Hypergraphs
  • 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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact