Andrzej Proskurowski

  • University of Oregon, Eugene, USA

According to our database1, Andrzej Proskurowski authored at least 84 papers between 1979 and 2023.

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



In proceedings 
PhD thesis 


Online presence:



Defensive domination in proper interval graphs.
Discret. Appl. Math., May, 2023

The complexity of the defensive domination problem in special graph classes.
Discret. Math., 2020

Foreword: Eighth Workshop on Graph Classes, Optimization, and Width Parameters, Toronto, Ontario, Canada.
Discret. Appl. Math., 2020

Seeing Arboretum for the (partial k-) Trees.
Proceedings of the Treewidth, Kernels, and Algorithms, 2020

Foreword: Sixth Workshop on Graph Classes, Optimization, and Width Parameters, Santorini, Greece, October 2013.
Discret. Appl. Math., 2016

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs.
J. Graph Theory, 2015

Qualitative bifurcation diagrams.
Expert Syst. J. Knowl. Eng., 2014

Obstructions for linear rank-width at most 1.
Discret. Appl. Math., 2014

Extremal graphs having no matching cuts.
J. Graph Theory, 2012

Intensive international Summer Schools in Global Distributed Software Development.
Proceedings of the IEEE Frontiers in Education Conference, 2012

Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs.
Theor. Comput. Sci., 2011

Obstructions for linear rankwidth at most 1
CoRR, 2011

A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition.
Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

Guest Editors' Foreword.
Discret. Appl. Math., 2010

Internationalization of computer science education.
Proceedings of the 41st ACM technical symposium on Computer science education, 2010

Guest editors' foreword.
Discret. Appl. Math., 2009

Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs.
Proceedings of the Algorithm Theory, 2008

Coloring mixed hypertrees.
Discret. Appl. Math., 2006

Generation of Graphs with Bounded Branchwidth.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

Qualitative Reasoning and Bifurcations in Dynamic Systems.
Proceedings of the MICAI 2006: Advances in Artificial Intelligence, 2006

On routing of wavebands for all-to-all communications in all-optical paths and cycles.
Theor. Comput. Sci., 2005

Priority-Consistent Graphs.
Electron. Notes Discret. Math., 2005

Structural decompositions, width parameters, and graph labelings.
Discret. Appl. Math., 2005

Embeddings of <i>k</i>-connected graphs of pathwidth <i>k</i>.
Discret. Appl. Math., 2005

Systems of distant representatives.
Discret. Appl. Math., 2005

Multi-source spanning trees: algorithms for minimizing source eccentricities.
Discret. Appl. Math., 2004

Spanners and message distribution in networks.
Discret. Appl. Math., 2004

Multicoloring trees.
Inf. Comput., 2003

The complexity of minimizing certain cost metrics for k-source spanning trees.
Discret. Appl. Math., 2003

On Routing of Wavebands for Gossiping in All-Optical Paths and Cycles.
Proceedings of the SIROCCO 10: Proceedings of the 10th Internaltional Colloquium on Structural Information Complexity, 2003

Geometric Systems of Disjoint Representatives.
Proceedings of the Graph Drawing, 10th International Symposium, 2002

Stable 2-pairs and (<i>X, Y</i>)-intersection graphs.
Discret. Math., 2001

Distance Constrained Labeling of Precolored Trees.
Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001

Maximum packing for k-connected partial k-trees in polynomial time.
Theor. Comput. Sci., 2000

Multi-Source Spanning Tree Problems.
J. Interconnect. Networks, 2000

Faster Algorithms for Subgraph Isomorphism of k-Connected Partial k-Trees.
Algorithmica, 2000

Memory Requirements for Table Computations in Partial k-Tree Algorithms.
Algorithmica, 2000

Hamiltonicity of Amalgams.
Graphs Comb., 1999

Classes of graphs with restricted interval models.
Discret. Math. Theor. Comput. Sci., 1999

Multi-coloring Trees.
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

Analysis of Algorithms for Listing Equivalence Classes of <i>k</i>-ary Strings.
SIAM J. Discret. Math., 1998

On the Complexity of Graph Covering Problems.
Nord. J. Comput., 1998

Minimum-time multidrop broadcast.
Discret. Appl. Math., 1998

Disjoint and unfolding domination in graphs.
Australas. J Comb., 1998

Algorithms for Vertex Partitioning Problems on Partial <i>k</i>-Trees.
SIAM J. Discret. Math., 1997

Covering Regular Graphs.
J. Comb. Theory B, 1997

Minimum Self-Repairing Graphs.
Graphs Comb., 1997

Complexity of Colored Graph Covers I. Colored Directed Multigraphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1997

Characterization and Complexity of Uniformly Non Primitive Labeled 2-Structures.
Theor. Comput. Sci., 1996

Plane Embeddings of 2-trees and Biconnected Partial 2-Trees.
SIAM J. Discret. Math., 1996

A generalization of line graphs: (<i>X, Y</i>)-intersection graphs.
J. Graph Theory, 1996

Bounded-call broadcasting.
Discret. Appl. Math., 1994

A Technique for Recognizing Graphs of Bounded Treewidth with Application to Subclasses of Partial 2-Paths.
Proceedings of the Graph Gramars and Their Application to Computer Science, 1994

Self-Repairing Networks.
Parallel Process. Lett., 1993

An Algebraic Theory of Graph Reduction.
J. ACM, 1993

Efficient Sets in Partial <i>k</i>-Trees.
Discret. Appl. Math., 1993

Practical Algorithms on Partial k-Trees with an Application to Domination-like Problems.
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Canonical Representations of Partial 2- and 3-Trees.
BIT, 1992

Graph reductions, and techniques for finding minimal forbidden minors.
Proceedings of the Graph Structure Theory, 1991

Report on GRA-GRA: 4th international workshop on graph grammars and their applications to computer science.
SIGACT News, 1990

Generating Binary Trees by Transpositions.
J. Algorithms, 1990

Forbidden minors characterization of partial 3-trees.
Discret. Math., 1990

Canonical Representation of Partial 2- and 3-Trees.
Proceedings of the SWAT 90, 1990

Monadic Second Order Logic, Tree Automata and Forbidden Minors.
Proceedings of the Computer Science Logic, 4th Workshop, 1990

On Parallel Complexity of the Subgraph Homeomorphism and the Subgraph Isomorphism Problem for Classes of Planar Graphs.
Theor. Comput. Sci., 1989

Centering a Spanning Tree of a Biconnected Graph.
Inf. Process. Lett., 1989

Linear time algorithms for NP-hard problems restricted to partial k-trees.
Discret. Appl. Math., 1989

Fast Parallel Algorithms for the Subgraph Homophormism and the Subgraph Isomorphism Problem for Classes of Planat Graphs.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1987

Interior graphs of maximal outerplane graphs.
J. Comb. Theory B, 1985

Binary Tree Gray Codes.
J. Algorithms, 1985

Problems on graphs with bounded decomposability.
Bull. EATCS, 1985

Separating subgraphs in k-trees: Cables and caterpillars.
Discret. Math., 1984

Concurrent Transmissions in Broadcast Networks.
Proceedings of the Automata, 1984

Networks immune to isolated line failures.
Networks, 1982

Directed Maximal-Cut Problems.
Inf. Process. Lett., 1982

Minimum Broadcast Trees.
IEEE Trans. Computers, 1981

Recursive Graphs, Recursive Labelings and Shortest Paths.
SIAM J. Comput., 1981

Minimum dominating cycles in outerplanar graphs.
Int. J. Parallel Program., 1981

Partitioning trees: Matching, domination, and maximum diameter.
Int. J. Parallel Program., 1981

Centers of maximal outerplanar graphs.
J. Graph Theory, 1980

On the Generation of Binary Trees.
J. ACM, 1980

Computation of the center and diameter of outerplanar graphs.
Discret. Appl. Math., 1980

Minimum dominating cycles in 2-trees.
Int. J. Parallel Program., 1979

Minimum broadcast graphs.
Discret. Math., 1979