Andreas Brandstädt

Affiliations:
  • University of Rostock, Institute of Computer Science, Germany


According to our database1, Andreas Brandstädt authored at least 162 papers between 1977 and 2024.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Finding dominating induced matchings in P10-free graphs in polynomial time.
Theor. Comput. Sci., 2024

2023
Combining decomposition approaches for the Maximum Weight Stable Set problem.
Theor. Comput. Sci., June, 2023

2022
Finding dominating induced matchings in P<sub>9</sub>-free graphs in polynomial time.
Discuss. Math. Graph Theory, 2022

2021
Maximum weight independent sets for (<i>S</i><sub>1, 2, 4</sub>, triangle)-free graphs in polynomial time.
Theor. Comput. Sci., 2021

Finding Efficient Domination for (P<sub>9</sub>, S<sub>1, 1, 6</sub>, S<sub>1, 2, 5</sub>-Free Chordal Bipartite Graphs in Polynomial Time.
CoRR, 2021

Finding Efficient Domination for P<sub>8</sub>-Free Bipartite Graphs in Polynomial Time.
CoRR, 2021

2020
Finding dominating induced matchings in S1, 1, 5-free graphs in polynomial time.
Discret. Appl. Math., 2020

Finding dominating induced matchings in S2, 2, 3-free graphs in polynomial time.
Discret. Appl. Math., 2020

On efficient domination for some classes of H-free chordal graphs.
Discret. Appl. Math., 2020

Dominating induced matchings in S1, 2, 4-free graphs.
Discret. Appl. Math., 2020

Finding Efficient Domination for S<sub>1, 1, 5</sub>-Free Bipartite Graphs in Polynomial Time.
CoRR, 2020

Finding Efficient Domination for S<sub>1, 3, 3</sub>-Free Bipartite Graphs in Polynomial Time.
CoRR, 2020

2019
A dichotomy for weighted efficient dominating sets with bounded degree vertices.
Inf. Process. Lett., 2019

On efficient domination for some classes of H-free bipartite graphs.
Discret. Appl. Math., 2019

Finding Dominating Induced Matchings in S<sub>1, 1, 5</sub>-Free Graphs in Polynomial Time.
CoRR, 2019

2018
Maximum weight independent set for ℓclaw-free graphs in polynomial time.
Discret. Appl. Math., 2018

Maximum Weight Independent Sets for (, triangle)-free graphs in polynomial time.
Discret. Appl. Math., 2018

Weighted efficient domination for some classes of H-free and of (H1, H2)-free graphs.
Discret. Appl. Math., 2018

Maximum Weight Independent Sets for (S<sub>1, 2, 4</sub>, Triangle)-Free Graphs in Polynomial Time.
CoRR, 2018

Efficient Domination and Efficient Edge Domination: A Brief Survey.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2018

2017
Bounding the Clique-Width of <i>H</i>-Free Chordal Graphs.
J. Graph Theory, 2017

On Efficient Domination for Some Classes of <i>H</i>-Free Chordal Graphs.
Electron. Notes Discret. Math., 2017

Efficient domination for classes of P<sub>6</sub>-free graphs.
Discret. Appl. Math., 2017

Dominating Induced Matchings in $S_{1, 2, 4}$-Free Graphs.
CoRR, 2017

Finding Dominating Induced Matchings in $S_{2, 2, 3}$-Free Graphs in Polynomial Time.
CoRR, 2017

On Chordal-k-Generalized Split Graphs.
CoRR, 2017

Finding Dominating Induced Matchings in P<sub>8</sub> -Free Graphs in Polynomial Time.
Algorithmica, 2017

2016
Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs.
Encyclopedia of Algorithms, 2016

Weighted Efficient Domination for P<sub>5</sub>-Free and P<sub>6</sub>-Free Graphs.
SIAM J. Discret. Math., 2016

Weighted efficient domination in two subclasses of P<sub>6</sub>-free graphs.
Discret. Appl. Math., 2016

Clique cycle-transversals in distance-hereditary graphs.
Discret. Appl. Math., 2016

Bounding the clique-width of H-free split graphs.
Discret. Appl. Math., 2016

Bounded Clique-Width of ($S_{1, 2, 2}$, Triangle)-Free Graphs.
CoRR, 2016

Weighted Efficient Domination for P_6 -Free and for P_5 -Free Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2016

2015
Addendum to: Maximum Weight Independent Sets in hole- and co-chair-free graphs.
Inf. Process. Lett., 2015

Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs.
Inf. Process. Lett., 2015

Maximum Weight Independent Sets in Odd-Hole-Free Graphs Without Dart or Without Bull.
Graphs Comb., 2015

The Dilworth Number of Auto-Chordal Bipartite Graphs.
Graphs Comb., 2015

Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds.
Discret. Appl. Math., 2015

Maximum Weight Independent Sets for ($P_7$, Triangle)-Free Graphs in Polynomial Time.
CoRR, 2015

Weighted Efficient Domination for $P_6$-Free Graphs in Polynomial Time.
CoRR, 2015

Dominating Induced Matchings for P<sub>8</sub>-free Graphs in Polynomial Time.
CoRR, 2015

Weighted Efficient Domination in Classes of P<sub>6</sub>-free Graphs.
CoRR, 2015

Efficient Domination for Some Subclasses of P<sub>6</sub>-Free Graphs in Polynomial Time.
CoRR, 2015

Weighted Efficient Domination for P<sub>5</sub>-Free Graphs in Linear Time.
CoRR, 2015

Efficient Domination for Some Subclasses of P_6 -free Graphs in Polynomial Time.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2015

Bounding the Clique-Width of H-free Chordal Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

2014
A note on efficient domination in a superclass of P<sub>5</sub>-free graphs.
Inf. Process. Lett., 2014

Preface.
Discret. Appl. Math., 2014

Weighted Efficient Domination for $(P_5+kP_2)$-Free Graphs in Polynomial Time.
CoRR, 2014

Dominating Induced Matchings for P 7-Free Graphs in Linear Time.
Algorithmica, 2014

2013
Corrigendum to "Cycle transversals in perfect graphs and cographs" [Theoret. Comput. Sci. 469(2013) 15-23].
Theor. Comput. Sci., 2013

Cycle transversals in perfect graphs and cographs.
Theor. Comput. Sci., 2013

New Polynomial Cases of the Weighted Efficient Domination Problem.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

2012
Maximum Weight Independent Sets in hole- and co-chair-free graphs.
Inf. Process. Lett., 2012

Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences.
Discret. Appl. Math., 2012

Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

2011
Path-Bicolorable Graphs.
Graphs Comb., 2011

On distance-3 matchings and induced matchings.
Discret. Appl. Math., 2011

Exploiting graph structure to cope with hard problems (Dagstuhl Seminar 11182).
Dagstuhl Reports, 2011

Dominating Induced Matchings for P7-Free Graphs in Linear Time
CoRR, 2011

Clique Separator Decomposition of Hole- and Diamond-Free Graphs and Algorithmic Consequences
CoRR, 2011

2010
Exact leaf powers.
Theor. Comput. Sci., 2010

Independent Sets of Maximum Weight in Apple-Free Graphs.
SIAM J. Discret. Math., 2010

Rooted directed path graphs are leaf powers.
Discret. Math., 2010

Characterising (k, <i>l</i>)-leaf powers.
Discret. Appl. Math., 2010

On Independent Vertex Sets in Subclasses of Apple-Free Graphs.
Algorithmica, 2010

Efficient Edge Domination on Hole-Free Graphs in Polynomial Time.
Proceedings of the LATIN 2010: Theoretical Informatics, 2010

2009
The complete inclusion structure of leaf power classes.
Theor. Comput. Sci., 2009

Simplicial powers of graphs.
Theor. Comput. Sci., 2009

A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers.
Discret. Math., 2009

Preface.
Discret. Appl. Math., 2009

2008
Structure and linear-time recognition of 4-leaf powers.
ACM Trans. Algorithms, 2008

Maximum Induced Matchings for Chordal Graphs in Linear Time.
Algorithmica, 2008

Ptolemaic Graphs and Interval Graphs Are Leaf Powers.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Independent Sets of Maximum Weight in Apple-Free Graphs.
Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

On k-Versus (k+1)-Leaf Powers.
Proceedings of the Combinatorial Optimization and Applications, 2008

2007
New applications of clique separator decomposition for the Maximum Weight Stable Set problem.
Theor. Comput. Sci., 2007

On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem.
Theor. Comput. Sci., 2007

The induced matching and chain subgraph cover problems for convex bipartite graphs.
Theor. Comput. Sci., 2007

Tree Spanners for Bipartite Graphs and Probe Interval Graphs.
Algorithmica, 2007

On ( <i>k</i> , <i>l</i>)-Leaf Powers.
Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

07211 Abstracts Collection - Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes.
Proceedings of the Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes, 20.05., 2007

2006
Clique-Width for 4-Vertex Forbidden Subgraphs.
Theory Comput. Syst., 2006

Structure and linear time recognition of 3-leaf powers.
Inf. Process. Lett., 2006

Distance-Hereditary 5-Leaf Powers.
Electron. Notes Discret. Math., 2006

<i>P</i><sub>6</sub>- and triangle-free graphs revisited: structure and bounded clique-width.
Discret. Math. Theor. Comput. Sci., 2006

Generalized Powers of Graphs and Their Algorithmic Use.
Proceedings of the Algorithm Theory, 2006

2005
On algorithms for (<i>P</i><sub>5</sub>, gem)-free graphs.
Theor. Comput. Sci., 2005

New Graph Classes of Bounded Clique-Width.
Theory Comput. Syst., 2005

Bisplit graphs.
Discret. Math., 2005

Chordal co-gem-free and (<i>P</i><sub>5</sub>, gem)-free graphs have bounded clique-width.
Discret. Appl. Math., 2005

On the structure of (<i>P</i><sub>5</sub>, gem)-free graphs.
Discret. Appl. Math., 2005

Clique-Width for Four-Vertex Forbidden Subgraphs.
Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

2004
Tree spanners on chordal graphs: complexity and algorithms.
Theor. Comput. Sci., 2004

Split-Perfect Graphs: Characterizations and Algorithmic Use.
SIAM J. Discret. Math., 2004

Efficient robust algorithms for the Maximum Weight Stable Set Problem in chair-free graph classes.
Inf. Process. Lett., 2004

Gem- And Co-Gem-Free Graphs Have Bounded Clique-Width.
Int. J. Found. Comput. Sci., 2004

On minimal prime extensions of a four-vertex graph in a prime graph.
Discret. Math., 2004

Preface: ODSA.
Discret. Appl. Math., 2004

(P<sub>5</sub>, diamond)-free graphs revisited: structure and linear time optimization.
Discret. Appl. Math., 2004

04221 Abstracts Collection - Robust and Approximative Algorithms on Particular Graph Classes.
Proceedings of the Robust and Approximative Algorithms an Particular Graph Classes, 23.05., 2004

2003
Structure and stability number of chair-, co-P- and gem-free graphs revisited.
Inf. Process. Lett., 2003

On the structure and stability number of P<sub>5</sub>- and co-chair-free graphs.
Discret. Appl. Math., 2003

On variations of P<sub>4</sub>-sparse graphs.
Discret. Appl. Math., 2003

Stability number of bull- and chair-free graphs revisited.
Discret. Appl. Math., 2003

On linear and circular structure of (claw, net)-free graphs.
Discret. Appl. Math., 2003

On the linear structure and clique-width of bipartite permutation graphs.
Ars Comb., 2003

Linear Time Algorithms for Some NP-Complete Problems on (P<sub>5</sub>, Gem)-Free Graphs.
Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

2002
Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
Inf. Process. Lett., 2002

On alpha-redundant vertices in P5-free graphs.
Inf. Process. Lett., 2002

Recognizing the P<sub>4</sub>-structure of claw-free graphs and a larger graph class.
Discret. Math. Theor. Comput. Sci., 2002

Tree Spanners on Chordal Graphs: Complexity, Algorithms, Open Problems.
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

2001
A note on alpha-redundant vertices in graphs.
Discret. Appl. Math., 2001

On Robust Algorithms for the Maximum Weight Stable Set Problem.
Proceedings of the Fundamentals of Computation Theory, 13th International Symposium, 2001

2000
Linear Time Algorithms for Hamiltonian Problems on (Claw, Net)-Free Graphs.
SIAM J. Comput., 2000

Efficiently Recognizing the <i>P</i> <sub>4</sub>-Structure of Trees and of Bipartite Graphs Without Short Cycles.
Graphs Comb., 2000

Recognizing the P<sub>4</sub>-structure of Block Graphs.
Discret. Appl. Math., 2000

On stable cutsets in graphs.
Discret. Appl. Math., 2000

1999
Convexity and HHD-Free Graphs.
SIAM J. Discret. Math., 1999

Distance Approximating Trees for Chordal and Dually Chordal Graphs.
J. Algorithms, 1999

Tree- and Forest-perfect Graphs.
Discret. Appl. Math., 1999

On the Stability Number of Claw-free P<sub>5</sub>-free and More General Graphs.
Discret. Appl. Math., 1999

Recognizing the P<sub>4</sub>-structure of Bipartite Graphs.
Discret. Appl. Math., 1999

1998
Dually Chordal Graphs.
SIAM J. Discret. Math., 1998

A linear-time algorithm for connected r-domination and Steiner tree on distance-hereditary graphs.
Networks, 1998

Powers of hhd-free graphs.
Int. J. Comput. Math., 1998

Corrigendum.
Discret. Math., 1998

The Complexity of some Problems Related to Graph 3-colorability.
Discret. Appl. Math., 1998

The Algorithmic Use of Hypertree Structure and Maximum Neighbourhood Orderings.
Discret. Appl. Math., 1998

1997
Homogeneously Orderable Graphs.
Theor. Comput. Sci., 1997

Clique <i>r</i>-Domination and Clique <i>r</i>-Packing Problems on Dually Chordal Graphs.
SIAM J. Discret. Math., 1997

Duchet-type theorems for powers of HHD-free graphs.
Discret. Math., 1997

LexBFS-orderings and powers of chordal graphs.
Discret. Math., 1997

Distance Approximating Trees for Chordal and Dually Chordal Graphs (Extended Abstract).
Proceedings of the Algorithms, 1997

1996
r-Dominating cliques in graphs with hypertree structure.
Discret. Math., 1996

Perfect elimination orderings of chordal powers of graphs.
Discret. Math., 1996

Partitions of graphs into one or two independent sets and cliques.
Discret. Math., 1996

Short Disjoint Cycles in Graphs with Degree Constraints.
Discret. Appl. Math., 1996

LexBFS-Orderings and Power of Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1996

1995
Homogeneously Orderable Graphs and the Steiner Tree Problem.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1995

1994
Dominating Cliques in Graphs with Hypertree Structures.
Proceedings of the STACS 94, 1994

Graphen und Algorithmen.
Leitfäden und Monographien der Informatik, Teubner, ISBN: 978-3-519-02131-5, 1994

1992
On Improved Time Bounds for Permutation Graph Problems.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1992

1991
Classes of bipartite graphs related to chordal graphs.
Discret. Appl. Math., 1991

Short Disjoint Cycles in Cubic Bridgeless Graphs.
Proceedings of the 17th International Workshop, 1991

1989
The Jump Number Problem for Biconvex Graphs and Rectangle Covers of Rectangular Regions.
Proceedings of the Fundamentals of Computation Theory, 1989

1987
The NP-Completeness of Steiner Tree and Dominating Set for Chordal Bipartite Graphs.
Theor. Comput. Sci., 1987

On Domination Problems for Permutation and Other Graphs.
Theor. Comput. Sci., 1987

Uniform Simulations of Nondeterministic Real Time Multitape Turing Machines.
Math. Syst. Theory, 1987

The Computational Complexity of Feedback Vertex Set, Hamiltonian Circuit, Dominating Set, Steiner Tree, and Bandwidth on Special Perfect Graphs.
J. Inf. Process. Cybern., 1987

Bipartite permutation graphs.
Discret. Appl. Math., 1987

1986
On Partitions of Permutations into Increasing and Decreasing Subsequences.
J. Inf. Process. Cybern., 1986

1985
On the restriction of some NP-complete graph problems to permutation graphs.
Proceedings of the Fundamentals of Computation Theory, 1985

1983
Zu Raum- und Zeitkompliziertheitsklassen auf nichtdeterministischen Turingakzeptoren.
PhD thesis, 1983

Space Classes, Intersection of Languages and Bounded Erasing Homomorphisms.
RAIRO Theor. Informatics Appl., 1983

Reversal-Bounded and Visit-Bounded Realtime Computations.
Proceedings of the Fundamentals of Computation Theory, 1983

1981
Closure Properties of Certain Families of Formal Languages with Respect to a Generalization of Cyclic Closure.
RAIRO Theor. Informatics Appl., 1981

Pushdown Automata with Restricted Use of Storage Symbols.
Proceedings of the Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31, 1981

1979
A Relation Between Space, Return and Dual Return Complexities.
Theor. Comput. Sci., 1979

1978
On a Family of Complexity Measures on Turing Machines, defined by Predicates.
J. Inf. Process. Cybern., 1978

1977
Eine Hierarchie beschränkter Rückkehrberechnungen auf on-line Turingmaschinen.
J. Inf. Process. Cybern., 1977


  Loading...