6 Search Results for "Spinrad, Jeremy P."

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-dev.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-dev.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-dev.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-dev.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-dev.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-dev.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 Corneil, Derek G.
  • 1 Hamburger, Peter
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms

  • Refine by Keyword
  • 2 approximation algorithms
  • 1 Cograph
  • 1 Graph algorithms
  • 1 Graph theory
  • 1 approximation
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2007
  • 1 1999
  • 1 2002
  • 1 2005
  • 1 2018

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