7 Search Results for "Kornst�dt, Andreas"

Document
DOI: 10.4230/DagRep.1.5.29
Exploiting graph structure to cope with hard problems (Dagstuhl Seminar 11182)

Authors: Andreas Brandstädt, Martin Charles Golumbic, Pinar Heggernes, and Ross McConnell

Published in: Dagstuhl Reports, Volume 1, Issue 5 (2011)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 11182 ``Exploiting graph structure to cope with hard problems'' which has been held in Schloss Dagstuhl -- Leibniz Center for Informatics from May 1st, 2011 to May 6th, 2011. During the seminar experts with a common focus on graph algorithms presented various new results in how to attack NP-hard graph problems by using the structure of the input graph. Moreover, in the afternoon of each seminar's day new problems have been posed and discussed.
Cite as

Andreas Brandstädt, Martin Charles Golumbic, Pinar Heggernes, and Ross McConnell. Exploiting graph structure to cope with hard problems (Dagstuhl Seminar 11182). In Dagstuhl Reports, Volume 1, Issue 5, pp. 29-46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{brandstadt_et_al:DagRep.1.5.29,
  author =	{Brandst\"{a}dt, Andreas and Golumbic, Martin Charles and Heggernes, Pinar and McConnell, Ross},
  title =	{{Exploiting graph structure to cope with hard problems (Dagstuhl Seminar 11182)}},
  pages =	{29--46},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{5},
  editor =	{Brandst\"{a}dt, Andreas and Golumbic, Martin Charles and Heggernes, Pinar and McConnell, Ross},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.1.5.29},
  URN =		{urn:nbn:de:0030-drops-32027},
  doi =		{10.4230/DagRep.1.5.29},
  annote =	{Keywords: Graph Classes, Graph Algorithms, NP-completeness, Width Parameters, Approximation Algorithms, Parameterized Complexity}
}
Document
DOI: 10.4230/DagSemProc.09051.6
The Dagstuhl Core

Authors: Theodor Dumitrescu, Johannes Kepper, Andreas Kornstädt, Daniel Röwenstruck, Perry Roland, Craig Sapp, and Eleanor Selfridge-Field

Published in: Dagstuhl Seminar Proceedings, Volume 9051, Knowledge representation for intelligent music processing (2009)

Abstract
A substantial number of workshop attendees were involved in an extensive discussion of musical features for which software support is desirable in the context of scholarly research and applications (printing, analysis, editing of virtual materials, and other activities). Some ability to interchange data among applications is also highly desired. At the present time (early 2009) two XML descriptions for music have been extensively discussed at other meetings and workshops. These are MusicXML (commercial) and the Music Encoding Initiative (MEI; non-commercial). Over continuing discussion in ensuing days, a list of ``core'' features was developed by a group including Ted Dumitrescu, Johannes Kepper, Andreas Kornstaedt, Daniel Roewenstrunk, Perry Roland, and Eleanor Selfridge-Field. Additional input was received from Craig Sapp, who has translated extensively among four of the five data representation schemes (Humdrum Kern, MuseData, SCORE, and MusicXML) compared on the ``core'' feature list. (At the present time, no software to implement MEI is available.) The representation schemes were chosen because of the extensive repositories of music that already exist in them. The list is a work-in-progress. A wiki (restricted access) has been set up at http://muwimedial.de/dagstuhl-core/. After a short phase of refinement, it will be made available more widely. The Dagstuhl Core is a means to facilitate the use of existing and creation of new polyphonic CWN corpora (1650-1935) by educating users about the possibilities and limitations of graphemic, application- independent music data formats and the quality of programs that convert between them. It provides a feature list for each format/converter containing ``Yes''/``No''/``by Extension'' with a concise description how the given feature can (not) be realised in a given format / by a given converter. Serving as a frame of reference for parties interested in using encoded music, as well as creating corpora, formats, and converters, the vast majority of Dagstuhl Core features should carry a ``Yes'' or ``by Extension'' for a music format to be considered a core format for representing music in CWN from 1650 to 1935. The emphasis of the ``core'' is intended to be less on completeness than on ``essential features'' that any representation approach intended for use in scholarly work should be able to handle. It is currently focused on European classical music of the eighteenth and nineteenth centuries.
Cite as

Theodor Dumitrescu, Johannes Kepper, Andreas Kornstädt, Daniel Röwenstruck, Perry Roland, Craig Sapp, and Eleanor Selfridge-Field. The Dagstuhl Core. In Knowledge representation for intelligent music processing. Dagstuhl Seminar Proceedings, Volume 9051, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{dumitrescu_et_al:DagSemProc.09051.6,
  author =	{Dumitrescu, Theodor and Kepper, Johannes and Kornst\"{a}dt, Andreas and R\"{o}wenstruck, Daniel and Roland, Perry and Sapp, Craig and Selfridge-Field, Eleanor},
  title =	{{The Dagstuhl Core}},
  booktitle =	{Knowledge representation for intelligent music processing},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9051},
  editor =	{Eleanor Selfridge-Field and Frans Wiering and Geraint A. Wiggins},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09051.6},
  URN =		{urn:nbn:de:0030-drops-19716},
  doi =		{10.4230/DagSemProc.09051.6},
  annote =	{Keywords: Music encoding, music interchange formats}
}
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 Brandstädt, Andreas
  • 4 Spinrad, Jeremy P.
  • 2 Jansen, Klaus
  • 1 Corneil, Derek G.
  • 1 Dumitrescu, Theodor
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Cograph
  • 1 Graph Algorithms
  • 1 Graph Classes
  • 1 Graph algorithms
  • Show More...

  • Refine by Type
  • 7 document

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

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