Andreas Brandstädt

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

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

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.
Discrete Applied Mathematics, 2019

Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time.
CoRR, 2019

Finding Dominating Induced Matchings in S1, 1, 5-Free Graphs in Polynomial Time.
CoRR, 2019

2018
Maximum weight independent set for ℓclaw-free graphs in polynomial time.
Discrete Applied Mathematics, 2018

Maximum Weight Independent Sets for (, triangle)-free graphs in polynomial time.
Discrete Applied Mathematics, 2018

Weighted efficient domination for some classes of H-free and of (H1, H2)-free graphs.
Discrete Applied Mathematics, 2018

Maximum Weight Independent Sets for (S1, 2, 4, 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 H-Free Chordal Graphs.
Journal of Graph Theory, 2017

On Efficient Domination for Some Classes of H-Free Chordal Graphs.
Electronic Notes in Discrete Mathematics, 2017

Efficient domination for classes of P6-free graphs.
Discrete Applied Mathematics, 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

On Efficient Domination for Some Classes of H-Free Chordal Graphs.
CoRR, 2017

Finding Dominating Induced Matchings in P8 -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 P5-Free and P6-Free Graphs.
SIAM J. Discrete Math., 2016

Weighted efficient domination in two subclasses of P6-free graphs.
Discrete Applied Mathematics, 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 and Combinatorics, 2015

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

Bounding the Clique-Width of H-free Split Graphs.
Electronic Notes in Discrete Mathematics, 2015

Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds.
Discrete Applied Mathematics, 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 P8-free Graphs in Polynomial Time.
CoRR, 2015

Weighted Efficient Domination in Classes of P6-free Graphs.
CoRR, 2015

Efficient Domination for Some Subclasses of P6-Free Graphs in Polynomial Time.
CoRR, 2015

Weighted Efficient Domination for P5-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 P5-free graphs.
Inf. Process. Lett., 2014

Preface.
Discrete Applied Mathematics, 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

Clique cycle transversals in distance-hereditary graphs.
Electronic Notes in Discrete Mathematics, 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.
Discrete Applied Mathematics, 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 and Combinatorics, 2011

On distance-3 matchings and induced matchings.
Discrete Applied Mathematics, 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. Discrete Math., 2010

Rooted directed path graphs are leaf powers.
Discrete Mathematics, 2010

Characterising (k, l)-leaf powers.
Discrete Applied Mathematics, 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.
Discrete Mathematics, 2009

Preface.
Discrete Applied Mathematics, 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 ( k , l)-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.
Electronic Notes in Discrete Mathematics, 2006

P6- and triangle-free graphs revisited: structure and bounded clique-width.
Discrete Mathematics & Theoretical Computer Science, 2006

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

2005
On algorithms for (P5, gem)-free graphs.
Theor. Comput. Sci., 2005

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

Bisplit graphs.
Discrete Mathematics, 2005

Chordal co-gem-free and (P5, gem)-free graphs have bounded clique-width.
Discrete Applied Mathematics, 2005

On the structure of (P5, gem)-free graphs.
Discrete Applied Mathematics, 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. Discrete 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.
Discrete Mathematics, 2004

Preface: ODSA.
Discrete Applied Mathematics, 2004

(P5, diamond)-free graphs revisited: structure and linear time optimization.
Discrete Applied Mathematics, 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 P5- and co-chair-free graphs.
Discrete Applied Mathematics, 2003

On variations of P4-sparse graphs.
Discrete Applied Mathematics, 2003

Stability number of bull- and chair-free graphs revisited.
Discrete Applied Mathematics, 2003

On linear and circular structure of (claw, net)-free graphs.
Discrete Applied Mathematics, 2003

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

Linear Time Algorithms for Some NP-Complete Problems on (P5, 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 P4-structure of claw-free graphs and a larger graph class.
Discrete Mathematics & Theoretical Computer Science, 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.
Discrete Applied Mathematics, 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 P 4-Structure of Trees and of Bipartite Graphs Without Short Cycles.
Graphs and Combinatorics, 2000

Recognizing the P4-structure of Block Graphs.
Discrete Applied Mathematics, 2000

On stable cutsets in graphs.
Discrete Applied Mathematics, 2000

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

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

Tree- and Forest-perfect Graphs.
Discrete Applied Mathematics, 1999

On the Stability Number of Claw-free P5-free and More General Graphs.
Discrete Applied Mathematics, 1999

Recognizing the P4-structure of Bipartite Graphs.
Discrete Applied Mathematics, 1999

1998
Dually Chordal Graphs.
SIAM J. Discrete 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.
Discrete Mathematics, 1998

The Complexity of some Problems Related to Graph 3-colorability.
Discrete Applied Mathematics, 1998

The Algorithmic Use of Hypertree Structure and Maximum Neighbourhood Orderings.
Discrete Applied Mathematics, 1998

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

Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs.
SIAM J. Discrete Math., 1997

Duchet-type theorems for powers of HHD-free graphs.
Discrete Mathematics, 1997

LexBFS-orderings and powers of chordal graphs.
Discrete Mathematics, 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.
Discrete Mathematics, 1996

Perfect elimination orderings of chordal powers of graphs.
Discrete Mathematics, 1996

Partitions of graphs into one or two independent sets and cliques.
Discrete Mathematics, 1996

Short Disjoint Cycles in Graphs with Degree Constraints.
Discrete Applied Mathematics, 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.
Discrete Applied Mathematics, 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.
Mathematical Systems Theory, 1987

The Computational Complexity of Feedback Vertex Set, Hamiltonian Circuit, Dominating Set, Steiner Tree, and Bandwidth on Special Perfect Graphs.
Elektronische Informationsverarbeitung und Kybernetik, 1987

Bipartite permutation graphs.
Discrete Applied Mathematics, 1987

1986
On Partitions of Permutations into Increasing and Decreasing Subsequences.
Elektronische Informationsverarbeitung und Kybernetik, 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.
ITA, 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.
ITA, 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.
Elektronische Informationsverarbeitung und Kybernetik, 1978

1977
Eine Hierarchie beschränkter Rückkehrberechnungen auf on-line Turingmaschinen.
Elektronische Informationsverarbeitung und Kybernetik, 1977


  Loading...